백준) 10844 - 쉬운 계단 수 [파이썬]

문제

45656이란 수를 보자.

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

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

입력

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

출력

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

예제 입력 1 

1

예제 출력 1 

9

예제 입력 2 

2

예제 출력 2 

17

---

dp = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
for n in range(1, int(input())):
    _dp = []
    for i in range(10):
        if i == 0: _dp.append(dp[1])
        elif i == 9: _dp.append(dp[8])
        else: _dp.append(dp[i-1] + dp[i+1])
    dp = _dp
print(sum(dp[1:]) % 1000000000)

---

풀이

 먼저 N = 1일 때 계단 수는 1, 2, 3, 4, 5, 6, 7, 8, 9 총 9개 이다.

N = 2 일 때 계단 수는 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 총 17개 이다.

N = 3 일 때 계단 수는 101, 121, 123, 210, 212, 232, 234, ...., 989 총 32 개 이다.

 이걸 계속 계산하는건 브루트 포스와 다름없는 풀이법이므로 여기서 규칙을 찾을 수 있어야한다.

 여기서 주의깊게 봐야하는 것은 모든 계단수는 0을 제외한 숫자로 시작한다는 것이다. 그러면 N = 3일 때 2로 시작하는 계단수를 살펴보자.

210, 212, 232, 234

 규칙을 찾았다면 글을 더 읽기전에 식을 세워보는 것을 추천한다.

 여기서 규칙은 2로 시작할 때 뒤에오는 숫자는 1, 3으로 시작하는 N = 2 일 때의 계단수 들이다.

그러면 이를 정리하면

N자리 계단수 중 M으로 시작하는 수의 개수는 는 M-1, M+1 로 시작하는 N-1자리의 합과 같다.

계단수의 개수를 식으로 표현해보면

	시작 숫자	1	2	3	4	5	6	7	8	9
N
1		1	1	1	1	1	1	1	1	1
2		2	2	2	2	2	2	2	2	1
3		3	4	4	4	4	4	4	3	2

가 된다.

M = 1 인 경우 0으로 시작하는 계단수에 대한 분기처리와 M = 9일 때 0은 계단수가 될 수 없기에 그에 대한 분기처리만 해주면 문제는 해결 가능하다.