134. 10844(쉬운 계단 수)

N = int(input())

dp = [[0 for _ in range(10)] for _ in range(101)]

for i in range(1,10):
    dp[1][i] = 1

for i in range(2,N+1):
    for j in range(10):
        if j == 0 :
            dp[i][j] = dp[i-1][1]
        elif j == 9:
            dp[i][j] = dp[i-1][8]
        else :
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
            
print(sum(dp[N]) % 1000000000)

문제요약

서로 1씩 차이가 나는 수를 계단수라고 함. 

길이 N이 주어졌을 때 계단수의 개수에 1000000000 을 나눈 나머지는 몇인가?

(ex 길이 1 => 1 2 3 4 5 6 7 8 9 길이 2 => 01 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98)

설명

길이가 2로 들어왔다고 가정해보자.

십의 자리 수에서 계단수는 01,10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98이다.

하지만 01은 십의자리 수가 아니므로 개수에서 빼준다.

그림을 그리면 다음과 같다.

이런식으로 계속 나아가면 된다.

예를들어 길이가 3이 들어왔으면,

다음과 같이 진행된다.

for i in range(1,10):
    dp[1][i] = 1

index가 0인 경우 모두 1이기 때문에 다음과 같이 1로 초기화 해준다.

0으로 시작하는 수는 계단수가 아니기 때문에 0에는 1로 초기화 하지 않는다.

 

for i in range(2,N+1):
    for j in range(10):
        if j == 0 :
            dp[i][j] = dp[i-1][1]
        elif j == 9:
            dp[i][j] = dp[i-1][8]
        else :
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

dp[인덱스][0~9] 로 생각하면 쉽다.

j = 0일때 => 0인 경우 1 값이 해당된다.

j = 9일때 => 9인 경우 8 값이 해당된다.

두 경우를 제외하고는 [이전 인덱스][자신의 수 -1] + [이전 인덱스][자신의 수 +1] 이 dp에 저장되게 된다.