[dp/백준] 10844번: 쉬운 계단 수

-문제: https://www.acmicpc.net/problem/10844

 

풀이 보면서 정수 삼각형이랑 비슷하다고 느낀 문제. 

처음에는 점화식이 dp[i]=dp[i-1]*2-1이라고 생각했는데 바로 틀렸다. 

이는 숫자에서 +-1을 하는데, 0은 -1이 안되므로 1밖에 없고, 9도 +1하면 10이라서 안되니까 8밖에 없어서 

0과 9일 때 제외는 모든 이전 자리수에서 가져오면 된다. 

 

-정답 풀이

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):#2부터 n자리 수까지
    for j in range(10): #0부터 9에 대해서 진행
        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])%(10**9))