[백준] 10844 쉬운 계단 수 (Python)

10844번: 쉬운 계단 수

문제

45656이란 수를 보자.

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

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

입력

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

출력

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

예제 입력 1 복사

1

예제 출력 1 복사

9

예제 입력 2 복사

2

예제 출력 2 복사

17

---

문제 풀이

 

0과 9를 제외하고는 다른 모든 수의 뒤에 나올 수 있는 경우의 수는 두가지다.

 

0부터 9까지 모든 수를 대상으로 마지막에 해당 수가 나올 수 있는 경우의 수를 생각 해 보자.

 

N이 1일 경우, [0,1,1,1,1,1,1,1,1,1] 로 나타난다.

 

N이 2인 경우를 살펴보자,

-0은 10 에서만 나올 수 있으므로 한가지

-1은 21 에서만 나올 수 있으므로 한가지 (01은 불가능하다.)

-9는 89 에서만 나올 수 있으므로 한가지

나머지는 각 수의 -1 혹은 +1에서 한개씩 해서 총 두개씩이다.

 

여기서 규칙을 살펴 보면 

0과 9를 제외한다면 i자리의 다른 모든 수가 마지막으로 나올 수 있는 경우의 수는

i-1자리의 앞과 뒤의 숫자의 합으로 나타난다.

 

이 것은 어찌보면 당연한데, 각 자리의 수 뒤에는 앞과 뒤 숫자만 나올 수 있기 때문이다.

---

코드

 

dp = [0] + [1 for _ in range(9)]
dp2 = [0 for _ in range(10)]


N = int(input())
for _ in range(N-1):
    for i in range(10):
        if i == 0:
            dp2[i] = dp[1]
        elif i == 9:
            dp2[i] = dp[8]
        else:
            dp2[i] = dp[i-1]+dp[i+1]
    dp = [i for i in dp2]
print(sum(dp))

---