기록공간

동적 계획법을 이용하여 해결하는 문제였다. 점화식을 찾기 위해 1부터 차례대로 구해보자. N = 1일 때는 1부터 9까지 모두 계단 수이다. (0은 계단 수가 아니라는 것을 명시했기 때문에 제외해야 한다) => 1, 2, 3, 4, 5, 6, ...., 9 이므로 N = 2일 때에는 계단 수는 다음과 같다. => 10, 21, 12, 32, 23, 43, 34, ...., 89 N = 2일 경우 계단 수에서 마지막 수를 잘 살펴보면 0 ~ 9까지 차례대로 나온다는 것을 알수 있고, 그 앞자리에는 +-1이 온다는 것을 알 수 있다. N = 2에서 마지막 수가 3일 경우 X3 (X에는 2와 4가 오기 때문에 N = 1에서 2와 4가 오면 된다.) 그러므로 23, 43이 계단수로 온다. N = 3에서 마지막 ..