[BOJ] 10884 쉬운 계단 수

N = int(input())
 
dp = [[0]*10 for _ in range(N)]
 
 
temp = [-1,1]
for i in range(N):
    for j in range(10):
        if i == N-1:
            if j == 0:
                continue
        if i == 0:
            dp[0][j] = 1
        else:
            for k in temp:
                nx = j+k
                if 0<=nx<10:
                    dp[i][j] += dp[i-1][j+k]
 
            
print(sum(dp[N-1])%1000000000)

dp 관련 문제이다.

 

이전 x-1축과 x축의 j 값이 1이 차는 경우를 더해주면 되는 것이다. 그리고 마지막 N-1 축까지 왔을 때 그때까지 누적된 수를 더해주면 된다.