[코딩 테스트 연습(파이썬/Python)] 백준 10844번 _ 쉬운 계단 수

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

10844번: 쉬운 계단 수

[문제]

45656이란 수를 보자.

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

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

 

[입력]

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

[출력]

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

 

[아이디어]

1) 다루는 수가 꽤나 커서 직접 모든 자리수를 탐색할 수는 없다.

2) 한 자리일 때부터, 자리 수가 늘어날 때마다 이전 자리 수에서의 계단 수를 기준으로 몇 개가 만들어지는지 구한다.

3) 하고 나서 보니 굳이 사전으로 할 필요도, 각각의 경우에 대해 모두 나눠서 할 필요도 없어보이긴한다.

(0의 상황은 특수하고, 1~8의 상황은 같으며, 9의 상황은 역시 특수하다.)

 

n=int(input())
def dic(n):
    d = dict()
    d[0] = 1
    for i in range(1,10):
        d[i]=1
    for _ in range(n-1):
        dd = dict()
        for i in range(0,10):
            if i ==0:
                dd[i] = d[i+1]
            elif i ==9:
                dd[i] = d[i-1]
            else:
                dd[i] = d[i+1] + d[i-1]
        d = dd
    return (sum(d.values()) - d[0])%1000000000
print(dic(n))