10844:쉬운계단수

https://www.acmicpc.net/problem/10844

틀린 풀이

직접

길이가 1인 계단수

길이가 2인 계단수

…

를 하나하나 구해보니

길이가 n인 계단 수 = 길이가 n-1인 계단수 * 2 -1 이라는 규칙이 나왔다.

하지만 계속 채점 결과는 틀렸다고 나옴..

맞는 풀이

이차원 배열로 품

* D[i][j] : 길이 i, 마지막 숫자가 j인 계단 수의 개수
* D[N][L] : N자리 계단수 마지막수는 L인 계단수의 개수
* D[N][L] = D[N-1][L-1] + D[N-1][L+1] (L : 1~8)
* D[N][0] = D[N][1]
* D[N][9] = D[N-1][8]