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

출처: 백준 온라인 저지
https://www.acmicpc.net/problem/10844

---

풀이 과정

처음에는 길이가 n인 계단 수의 개수를 f(n)이라고 두고, 이에 대한 점화 관계를 찾으려고 했다. 하지만 0이나 9 다음에는 하나의 수만 올 수 있으며, 0으로는 수가 시작할 수 없다는 조건 때문에 점화 관계를 구하기 어려웠다. 끝이 0, 1, 8, 9로 끝나는 경우를 따로 세는 방법도 생각해보았으나, 그럴 경우 너무 복잡해졌다.

그러다가 문제를 다시 풀고자 했을 때, 여러 동적 프로그래밍 문제가 2차원 배열의 점화 관계로 해결되었던 것을 생각해냈다. 그래서 계단 수의 자리 수뿐만 아니라 끝나는 숫자를 함께 고려한 2차원 표를 그려보았다.

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

위 행렬을 stairs라고 할 때, stairs[i][j + 1]는 j로 끝나는 i자리 수의 계단 수를 의미한다. 예를 들어, 5로 끝나는 3자리 수의 계단 수의 개수는 stairs[3][6] = 4다.

위 표에서는 어렵지 않게 규칙을 찾을 수 있다. 어떤 N자리 수의 계단 수가 숫자 M으로 끝난다고 하자. 그렇다면 그 수는 N-1자리 수의 계단 수의 뒤에 숫자 M을 붙인 것과 같다. 그리고 전체 수가 계단 수가 되려면, M 앞의 계단 수는 M-1 또는 M+1로 끝나야 한다. 따라서 이를 점화 관계로 표현하면 다음과 같다.

$S[i][j] = S[i - 1][j - 1] + S[i - 1][j + 1]$

다만 0으로 끝나는 N자리 계단 수의 경우, 그 앞의 숫자로 -1이 올 수는 없으므로, 그 앞이 1로 끝나는 경우만을 계산한다. 따라서 $S[i][0] = S[i - 1][1]$이다.

마찬가지의 원리로 $S[i][9] = S[i - 1][8]$이다.

최종 풀이

from sys import stdin


n = int(stdin.readline())

stairs = [[0] * 10 for _ in range(n + 1)]

# 초기값 설정
stairs[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(2, n + 1):
    # 계단 수가 0으로 끝나는 경우
    stairs[i][0] = stairs[i - 1][1]
    # 계단 수가 9로 끝나는 경우
    stairs[i][9] = stairs[i - 1][8]
    
    # 계단 수가 1~8로 끝나는 경우
    for j in range(1, 9):
        stairs[i][j] = stairs[i - 1][j - 1] + stairs[i - 1][j + 1]


print(sum(stairs[n]) % 1000000000)