[백준][DP] 10844. 쉬운 계단 수

10844. 쉬운 계단 수

 

 

• 풀이
  • 앞자리 수가 0일 때는 뒷자리수가 1
  • 앞자리 수가 9일 때는 뒷자리수가 8 밖에 되지 못함
  • 나머지 수는 앞자리 k 일 때, 뒷자리가 k-1, k+1만 올 수 있음
   

 

• a[n][k] : n자리에 k 값
• a[n][k]= a[n-1][k-1]+ a[n-1][k+1]
  • 현재 자리에 올수있는 값을 계산하면
  • 앞의 자리에서 나보다 -1 , +1 인 애들만 가능
  • 대신 0일때, 9일때만 조건

 

INF = 1000000000

n = int(input())

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

dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
for i in range(2, 101):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i-1][1] % INF
            continue
        if j == 9:
            dp[i][j] = dp[i-1][8] % INF
            continue
        dp[i][j] = (dp[i-1][j-1]+dp[i-1][j+1]) % INF

print(sum(dp[n]) % INF)