백준 10844 : 쉬운 계단 수

이 문제는 자리수가 주어지면 해당 자릿수의 계단 수의 경우의 수를 구하는 문제이다.

여기서 문제에서 정의하는 계단 수는 인접한 각 자리의 수가 1의 차이로 연속되는 것을 말한다. 

문제에서 예시로 든 45656또한 1의 차이로 연속되고 있다. 다만 0~9까지의 수, 즉 1의 자릿수를 가질 때 이 문제는 1~9까지 또한 계단 수로 정의하고 있다. 이 부분은 예제에서 제시가 되고 있기 때문에 납득하면 될 것 같다.

 

이 문제를 어떻게 해결해야 할까? 우선 1의 자릿수 일 때 계단 수를 써보자.

1, 2, 3, 4, 5, 6, 7, 8, 9

0으로 시작되는 계단 수가 없으니 0은 제외한다.

2의 자릿수를 가질 때는

10, 12, 21, 23, 32, 34, 43, 45, 54, 56, .... , 87, 89, 98이다.

3의 자릿수를 가질 때는

101, 121, 123, 210, 212 ..., 898, 987, 989이다.

 

항상 마지막 숫자는 그 전의 숫자의 -1, +1이 되는 법칙이 있다.

다만 그 전의 숫자가 0일 때는 +1만 가능하고 (0에서 -1을 하면 -1이기 때문에), 9일 때는 -1만 가능하다. (9에서 +1을 하면 10이기 때문에)

그렇다면 이 문제는 이 전의 자릿수를 알면 해당 자릿수를 구할 수 있는 다이나믹 프로그래밍 문제임을 생각해내야 한다.

항상 이전 자릿 수의 값으로 현재 자릿 수의 값을 구해내는 결정dp 테이블을 만들어보면

d[자릿수][해당 자릿수의 값] = 해당 자릿수의 값으로 끝나는 경우의 수로 만들면 된다. 

즉 자릿수가 2가 주어지고 해당 자릿수의 값이 3이라면! 그 전의 수가 2로 끝나거나(or), 4로 끝나야 한다.

d[2][3] = d[1][2] + d[1][4]가 되는 것이다.

하지만 자릿수가 2이고 0으로 끝날 때는 그 전의 수가 1일 경우 밖에 없기 때문에,

d[2][0] = d[1][1]

자릿수가 동일하고 9로 끝날 때는, 그 전의 수가 8일 경우 밖에 없다.

d[2][9] = d[1][8]

 

이를 점화식으로 표현하면 i가 1에서 8일 때는 d[N][i] = d[N-1][i-1] + d[N-1][i+1]이 된다.

0일 때는 d[N][i] = d[N-1][i+1], 9일 때는 d[N][i] = d[N-1][i-1] 이다.

 

 

포맷에 맞는 2차원 리스트를 만들고, 자릿수가 1일 때 0을 제외한 값에 1을 배정한다! 

N = int(input())

d = [[0]*10 for _ in range(N+1)]

for i in range(1, len(d[1])):
    d[1][i] = 1

for i in range(2, len(d)):
    for j in range(len(d[i])):
        if j == 0 : d[i][j] = d[i-1][j+1]
        elif j == 9 : d[i][j] = d[i-1][j-1]
        else : d[i][j] = d[i-1][j-1] + d[i-1][j+1]

print(sum(d[N])%1000000000)