[BOJ]10844. 쉬운 계단 수

문제:

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질

때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력:

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

출력:

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

풀이 방법:

길이가 하나 길어질수록 그 전의 길이에 영향을 받는다. 임의의 숫자 n에 대해서 생겨지는 계단 수의 수는 이전의 n-1 과 n+1의 수의 합이다. 하지만 끝값 0이나 9와 같은 경우에는 계단수를 유지하기 위해 각각 1과 8만 와야 하므로 이 경우에 대해서만 더해주도록 한다.

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