기록공간

역시 동적계획법을 사용하여 푸는 문제이다. 우선 규칙을 살펴보자. 피보나치 규칙인 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...