기록공간

동적 계획법을 사용하여 해결하는 문제였다. N번째에서 최대가 되는 연속합은 두가지 경우가 있다. 1. N-1번째의 연속합과 N번째 값을 더한 것 2. N번째 값 (N번째 부터 연속합을 구하는 경우) 이 두가지 경우를 점화식으로 만들면 다음과 같다. N번째의 연속합을 기록할 DP테이블 배열 DP[N+1](인덱스 접근시 0부터 시작하므로)과 해당 번째의정수를 기록할 배열 num[N+1]이 있다고 했을때, 첫번째 경우는 DP[N] = DP[N-1] + num[N]이고, 두번째 경우는 DP[N] = num[N]이 된다. 이 둘중 가장 큰 값이 DP[N]에 알맞는 연속합 값이 된다. 1번째 부터 마지막 번째 까지 알맞는 DP값을 기록한 후 DP 배열 중 가장 큰 값이 이 문제의 결과값이 된다. 주의할 점은 음수가..

동적 계획법을 사용하여 해결하는 문제이다. 연속으로 놓여있는 3잔을 마실 수 없기 때문에 세가지 경우가 도출된다. N개의 와인잔이 있다고 가정했을때, 처음부터 N번째 까지 차례대로 최대로 마신 양을 기록한다고 하자. N번째 와인잔에서는... 1. 해당 번째 와인을 마시지 않는 경우 : 그러면 이전 와인에서 최대로 마신 양이 된다. 2. 해당 번째 와인을 마시고 이전이전 와인을 마시는 경우 : 그러면 이전이전 와인에서 최대로 마신 양과 N번째 와인의 양의 합이다. 3. 해당 와인을 마시고 이전 와인을 마시고, 3잔 이상인 경우, 연속으로 놓여있는 3잔을 마실 수 없기 때문에 이전이전이전 와인을 마신다 : 이전이전이전 와인에서 최대로 마신 양과 이전 와인와 양 그리고 N번째 와인의 양를 모두 더한다. 이제 ..

동적계획법을 사용하는 문제이다. 아래 층에 있는 수를 선택 할때에는 대각선 왼쪽과 오른쪽 중 하나만 선택이 가능하다는 조건을 상기하며 살펴보도록 하자. 층마다 저장해야 할 정수 값들이 늘어난다. 그렇기 때문에 값을 저장할때나 DP테이블로 사용할때 2차원 배열이 필요하다. 맨 위에 값은 하나이기 때문에 DP테이블에 맨 윗층은 한개의 값이 저장된다. 그리고 2층은 값이두개가 되며 맨 위층의 값과 더하여 DP 테이블에 2개의 값이 저장된다. 여기서 특성을 알수 있는데 양 사이드에 있는 값들은 무조건 왼쪽 값은 그 위층의 맨 왼쪽값과만 더할 수 있고, 오른쪽 값은 그 위층의 맨 오른쪽 값과만 더할 수 있다. 그리고 3층은 값이 세개가 되며 양 사이드 2개의 값은 위와 같은 규칙으로 더해지고, 중간 값 하나는 2..

동적 계획법을 이용하는 문제였다. 규칙을 먼저 살펴 보도록 하겠다. 1자리 -> 1 => 1개 2자리 -> 10 => 1개 3자리 -> 100, 101 => 2개 4자리 -> 1000, 1001, 1010 => 3개 5자리 -> 10000, 10001, 10100, 10101, 10010 => 5개 .... 피보나치 수열과 같은 규칙을 보이고 있다. F[i] = F[i - 2] + F[i - 1] 하지만 90자리 까지 구한다는 점에 주의를 하자. 90자리까지 표현하려면 int 범위로는 부족하기 때문이다. 코드는 다음과 같다. #include using namespace std; int main() { unsigned long long dp[90 + 1]; int input; cin >> input; dp..

동적계획법을 사용하는 문제였다. 이번 문제는 다른 문제들과 다르게 DP 테이블을 2차원 배열로 만들어줘야 한다. 한 경우(집)에 3가지 값(RGB)을 DP 테이블에 기록해야 하기 때문이다. 예를들어 어떤 집 N을 R로 칠할경우, 전 집 N - 1은 R로 칠할 수 없으므로 G와 B로 칠하는 비용중 가장 작은 비용을 찾아 N의 R로 칠하는 비용을 더해 DP 테이블에 기록하면 된다. N에서 G와 B도 위와 같은 방법으로 해주면 된다. DP(N에서 R) = DP(N - 1에서 G나 B중 가장 작은 값) + H(N에서 R) DP(N에서 G) = DP(N - 1에서 R나 B중 가장 작은 값) + H(N에서 G) DP(N에서 B) = DP(N - 1에서 R나 G중 가장 작은 값) + H(N에서 B) (DP는 DP테이..

동적계획법을 사용하는 문제이다. 2x1 크기부터 타일을 채울 수 있는 방법의 수를 그려보면 다음과 같은 결과가 나온다. 2x1 => 1개 2x2 => 2개 2x3 => 3개 2x4 => 5개 ..... 규칙을 보면 피보나치와 같다. F[i] = F[i - 2] + F[i - 1] 하지만 2x1000까지 방법의 수는 int로 표현할 수 없으며 10007를 나눈 나머지를 출력하라고 하였기 때문에 방법의 수를 10007로 나눈 값을 dp 테이블에 기록하면 된다. 코드는 다음과 같다. #include using namespace std; int main() { int dp[1000 + 1]; int input; cin >> input; dp[0] = 0; dp[1] = 1; dp[2] = 2; for (int ..

동적계획법을 사용하는 문제였다. 규칙 계단을 오른때는 1칸 또는 2칸 오를 수 있다. 연속된 3칸을 오를 수 없다. 마지막 계단은 무조건 밟아야한다. 위 3가지 규칙을 바탕으로 마지막 계단을 밟는 경우를 두가지로 분류 해볼 수 있다. 1. 마지막 계단을 밟고 그 전 계단을 밟는 경우 (하지만 위 규칙 2번으로 인해 무조건 전 계단을 밟은 이후 전전전 계단을 밟아야 한다.) 이 경우 점화식은 S[n] = S[n] + S[n - 1]이 된다. (위 규칙 2번으로 인해 DP[n - 3]도 더해줘야 한다.) (S는 계단의 값들을 보관하는 배열이고 DP는 계단까지의 최대값을 보관하는 DP테이블(배열)이다.) 2. 마지막 계단을 밟고 그 전전 계단을 밟는 경우 이 경우 점화식은 S[n] = S[n] + DP[n -..

역시 동적계획법을 사용하여 푸는 문제이다. 우선 규칙을 살펴보자. 피보나치 규칙인 F(N) = F(N - 1) + F(N - 2)를 염두해두고 보자. * N이 0일때 0 호출 횟수 = 1 1 호출 횟수 = 0 * N이 1일때 0 호출 횟수 = 0 1 호출 횟수 = 1 * N이 2일때 0 호출 횟수 = (1일때 0 호출 횟수) + (0일때 0 호출 횟수) = 0 + 1 = 1 1 호출 횟수 = (1일때 1 호출 횟수) + (0일때 1 호출 횟수) = 1 + 0 = 1 * N이 3일때 0 호출 횟수 = (2일때 0 호출 횟수) + (1일때 0 호출 횟수) = 1 + 0 = 1 1 호출 횟수 = (2일때 1 호출 횟수) + (1일때 1 호출 횟수) = 1 + 1 = 2 0과 1의 호출 횟수가 필요하기 때문에 ..