기록공간

동적계획법을 사용하여 푸는 문제이다. 우선 규칙을 먼저 살펴보자. * 정수 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...