기록공간

동적계획법을 사용하는 문제이다. 아래 층에 있는 수를 선택 할때에는 대각선 왼쪽과 오른쪽 중 하나만 선택이 가능하다는 조건을 상기하며 살펴보도록 하자. 층마다 저장해야 할 정수 값들이 늘어난다. 그렇기 때문에 값을 저장할때나 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의 호출 횟수가 필요하기 때문에 ..

동적계획법을 사용하는 문제이다. 규칙을 먼저 살펴보자. * 1일 경우 1 -> 1개 * 2일 경우 1 + 1 2 -> 2개 * 3일 경우 1 + 1 + 1 2 + 1 1 + 2 3 -> 4개 * 4일 경우 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 2 + 1 + 1 2 + 1 1 + 3 3 + 1 -> 7개 (혹은 F(3) + F(2) + F(1) = 4 + 2 + 1 = 7) * 5일 경우 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 1 + 2 + 1 + 1 1 + 1 + 2 + 1 1 + 1 + 1 + 2 2 + 2 + 1 2 + 1 + 2 1 + 2 + 2 3 + 1 + 1 1 + 3 + 1 1 + 1 + 3 2 + 3 3 + 2 -> 13개 (혹은 F(4) + F(3..

동적계획법을 사용하여 푸는 문제이다. 우선 규칙을 먼저 살펴보자. * 정수 2 1. 1을 빼면 1이 된다. 2. 2로 나누어 떨어지고 1이 된다. 3. 3으로 나누어 떨어지지 않는다. -> 정수 2를 1로 만드는 최소 횟수는 1이다. * 정수 3 1. 1을 빼면 2가 된다. 정수 2에서 1로 되는 최소 횟수는 1이다. 그러므로 1 + 1 = 2이다. 2. 2로 나누어 떨어지지 않는다. 3. 3으로 나누어 떨어지고 1이 된다. -> 정수 3을 1로 만드는 최소 횟수는 1이다. * 정수 4 1. 1을 빼면 3이 된다. 정수 3에서 1로 되는 최소 횟수는 1이다. 그러므로 1 + 1 = 2이다. 2. 2로 나누어 떨어지고 2가 된다. 2에서 1로 되는 최소 횟수는 1이다. 그러므로 1 + 1 = 2이다. 3...