연잎의 develog

코딩테스트 연습 - 합승 택시 요금 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr [문제] 택시 합승을 이용해서 요금을 최대한 줄여야하는 문제이다! [해결전략] 처음엔 그래프만 보..

12852번: 1로 만들기 2 (acmicpc.net) 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net [문제] [해결전략] 예전에 같은문제를 bfs로 푼적이 있었는데 오늘은 dp로 풀어볼것이다! 1로만들기 1 문제와 다른점이 있다면 최소횟수에 덧붙여서 n -> 1까지 도달하는 경로도 출력해주어야한다는 것이다! 그래서 pre라는 경로복원용 테이블을 만들어서 pre[i] = j 즉, i->j 로 가는 것이 최적횟수 임을 저장하자! [풀이] #include #include using namespace std; const int MAX = 1000000; int dp[MAX + 1] = { 0, }; int pre[MAX..

11726번: 2×n 타일링 (acmicpc.net) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net [문제] 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. [해결전략] : 본문제가 처음부터 dp로 풀어야하는 문제라는 것을 알아차리기는 쉽지 않다. n의 크기를 하나씩 늘려가며 직접 경우의 수를 세보면, 규칙성이 발견된다! 그 규칙을 이용해 점화식을 세워주면 dp로 쉽게 해결할 수 있다. 1. 테이블 정의하기 dp[i] = 2 x i 크기의 직사각형을 채우는 방법의 수 2. 점화식 ..

2579번: 계단 오르기 (acmicpc.net) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net [문제] [해결전략] 만일 n이 그다지 크지 않았다면, 백트래킹과 같은 방식으로 O(2^N)만에 해결이 가능하지만 지금 처럼 N이 300일때는 어림도 없다 따라서 DP 를 통해 해결해주어야한다. 1. 테이블 정의하기 dp [i] = i번째 계단까지 올라섰을 때 점수 합의 최댓값 만일 위와 같이 테이블을 정의하게 되면 연속한 세계단을 모두 밟을 수 없다는 제약조건을 점화식에 넣을 방법이 없다..! 따라서 테이블을 다른 방식으로..

9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net [문제] 수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오 [해결전략] 1. 테이블 정의하기 dp [i] = 정수 i 를 1,2,3 의 합으로 나타내는 경우의 수 2. 점화식 찾기 한번에 점화식을 찾기는 어려우므로 한번 실제 숫자를 대입시켜서 예시와 함께 생각해보자!..

1463번: 1로 만들기 (acmicpc.net) 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net [문제] [해결전략] 사실 이문제는 해결한 적이 있다. 처음에 이문제를 bfs 로 풀었었는데 오늘은 dp로 한번 더 풀어보려고한다! dp 문제는 보통 4단계로 해결할 수 있다. 1. 테이블 정의하기 dp [i] = i를 1로 만들기 위해 필요한 연산 횟수의 최솟값 2. 점화식 찾기 한번에 점화식을 찾기는 어려우므로 한번 실제 숫자를 대입시켜서 예시와 함께 생각해보자! dp [1] ~ dp[11] 의 값을 모두 알고 있는 상황에서 dp[12] 의 값을 구해야한다면? 3으로 나누거나 (dp [12] = dp[4] + 1 ) 2으로..

[백준/5622]다이얼 : 네이버 블로그 (naver.com) [백준/5622]다이얼 c++ 5622번: 다이얼 (acmicpc.net) 상근이의 할머... blog.naver.com [문제] [해결전략] 처음에 문제를 읽기전에 내가 알던 보통의 다이얼을 떠올리면서 queue를 이용해야하나? 생각하고 있었는데 이 다이얼은 다음 숫자를 누르기 전에 처음위치로 다시 돌아가는 특성을 지니고 있다. 그리고 i번째 숫자를 누르기 위해서는 i+1초가 필요하다. 따라서 그냥 복잡하게 처리할 필요없이 (알파벳이 어떤 숫자에 위치해 있는지 + 1 ) 을 계속해서 더해주면 된다. 예를들어 UNUCIC 는 868242 인데 9 + 7 + 9+ 3+ 5 + 3 = 36 을 계산해..

2580번: 스도쿠 (acmicpc.net) 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net [문제] [해결전략] 1. blank 벡터에 빈칸좌표를 pair 형태로 모두 담는다. 2. dfs 로 idx(몇번째 빈칸을 처리하고 있는지) 를 넘겨주면서 빈칸을 하나씩 채워나간다. 이때 유효하지 않는 값이 채워지면 재귀가 더 깊숙히 수행되지 않도록 백트래킹을 활용한다. 이때 빈칸에 해당 숫자가 들어가도 되는 지 확인하기 위해 check (row,col,num) 함수를 이용한다. 이 함수는 (row.col)에 num ..

2638번: 치즈 (acmicpc.net) 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net [문제] [해결전략] 단순히 치즈공간 : 1 , 치즈가 없는 공간: 0 으로 표시해 두면이상이 치즈가 없는공간과 접촉해있으면 다음턴에 치즈를 녹여야겠다하고 생각할 수도 있다! 그런데 이 문제는 치즈 내부공간과 치즈 외부공간을 분리하고 있다. 따라서 치즈공간 : 1 , 치즈가 없는 내부 공간: 0 , 치즈가 있는 외부 공간: -1 으로 표시하고 두면이상이 치즈 외부공간(-1) 과 접촉해 있을때만 치즈를 녹여야..

2776번: 암기왕 (acmicpc.net) 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net [문제] [해결전략] 1 ≤ N ≤ 1,000,000 이므로 N이 굉장히 크다. 따라서 숫자찾기를 최대한 빠른 시간 내에 마쳐야한다. set,map,이분탐색 등 여러가지 방법을 활용해볼 수 있다. [풀이] 1. set을 이용한 풀이 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.ti..