백준 10844번: 쉬운 계단 수 (Python) TODO

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

---

 

풀이

1) 1자리 수인 경우: 인접한 수가 없으니, 모든 수에 대해 vacuously true이다. 9개(그냥 9개라 문제에서 제시했다고 생각해도 무방할 듯 하다.)

2) 2자리 수인 경우: 10, 21, ... , 98 and 21, 32, ... , 89 총 17개이다.

3) 3자리 이상인 경우

이제는 규칙을 발견해야 한다. N자리 계단 수를 찾기 위해, N-1자리 계단 수에서 수를 하나 더 붙인다고 생각해보자. 

(당연하지만, 이 풀이는 N자리 계단수의 앞의 N-1자리도 당연히 계단수이기 때문에 성립하는 풀이이다.)

앞자리를 고려하는 풀이 방법도 있던데, 맨 뒷자리 값에 따라 분류해보도록 한다.

1. 끝자리가 0인 경우: 계단수가 되려면 뒤에 1을 붙여야 한다.
2. 끝자리가 1~8인 경우: 계단수가 되려면 뒤에 0or2(1인 경우), 1or3(2인 경우), ... , 7or9(8인 경우)를 붙여야 한다.
3. 끝자리가 9인 경우: 계단수가 되려면 뒤에 8을 붙여야 한다.

그러면, 'i자리 숫자 중 끝이 j로 끝나는 계단 수'의 개수를 dp[i][j]라 정의한다. row는 10개, column은 N+2개로 한다(범위를 N+1까지로 하면 93% 즈음에서 IndexError가 발생한다. 코드를 보면 j == N+1인 경우가 없는데, 왜 그럴까???).

 

코드

MOD = 1000000000
N = int(input())
dp = [[0]*10 for _ in range(N+2)]

dp[2] = [1, 1, 2, 2, 2, 2, 2, 2, 2, 1]

if N == 1:
    print(9)
        
elif N == 2:
    print(17)

else:
    for i in range(3, N+1):
        dp[i][0] = dp[i-1][1]
        for j in range(1, 9):
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % MOD
        dp[i][9] = dp[i-1][8]
    print(sum(dp[N]) % MOD)

 

TODO:

앞자리로 점화식 구해서 그것도 적어보기. 지금 너무 피곤해