[백준 10844] 쉬운 계단 수 with Python

문제 링크

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

10844번: 쉬운 계단 수

풀이

N = int(input())
dp = [[0]*10 for _ in range(N+1)]
dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
for i in range(2, N+1):
    for j in range(10):
        if j == 0:
            dp[i][0] = dp[i-1][1]
        elif j == 9:
            dp[i][9] = dp[i-1][8]
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

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

길이가 N인 계단 수를 만드려면 길이가 N-1인 계단 수의 뒤에 그 마지막 숫자와 1 차이나는 숫자를 붙이면 된다.

 

길이가 N-1인 계단 수의 마지막 숫자가 0이라면 1 하나만 붙을 수 있고,

마지막 숫자가 1이라면 0, 2 두 개가 붙을 수 있고,

마지막 숫자가 2라면 1, 3 두 개가 붙을 수 있다.

 

즉, 길이가 N-1인 계단 수 중에서

마지막 숫자가 0으로 끝나는 수는 1로 끝나는 길이가 N인 계단 수를 만들 수 있고,

마지막 숫자가 1로 끝나는 수는 0, 2로 끝나는 길이가 N인 계단 수를 만들 수 있고,

마지막 숫자가 2로 끝나는 수는 1, 3으로 끝나는 길이가 N인 계단 수를 만들 수 있다는 뜻이다.

 

이것을 반대로 생각하면

길이가 N인 계단 수 중에서 0으로 끝나는 수의 개수는

길이가 N-1인 계단 수 중에서 1로 끝나는 수의 개수와 같고,

길이가 N인 계단 수 중에서 1로 끝나는 수의 개수는

길이가 N-1인 계단 수 중에서 0 또는 2로 끝나는 수의 개수와 같다는 뜻이다.

 

표로 정리하면 아래와 같다.

길이가 N인 계단 수의 마지막 숫자	길이가 N-1인 계단 수의 마지막 숫자 (길이가 N인 계단 수의 끝에서 두 번째 숫자)
0	1
1	0, 2
2	1, 3
3	2, 4
4	3, 5
5	4, 6
6	5, 7
7	6, 8
8	7, 9
9	8

 

dp[N]은 길이가 10인 배열을 가리키며,

이 배열의 각 인덱스에는 해당 인덱스로 끝나는 길이가 N인 계단 수의 개수가 저장된다.

길이가 1인 계단 수는 1, 2, 3, 4, 5, 6, 7, 8, 9가 있으므로,

dp[1]은 [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]가 된다.

 

dp[N][0]은 dp[N-1][1]과 같고, dp[N][9]는 dp[N-1][8]과 같으며,

이 외에 나머지(1~8)를 j라고 할 때

dp[N][j] = dp[N][j-1] + dp[N][j+1]로 나타낼 수 있다.