[백준, 10844번] 쉬운 계단 수

우선 문제 이해에 대한 어려움이 컷다

• dp를 저장할 배열을 어떻게 만들어야하는지에 대한 어려움도 크게 다가왔다.
  • 그래서 n+1의 수만큼 배열을 만들어 n+1차원 배열을 만들어 문제를 해결
• 이후 n = 1의 경우엔 1~9까지 모두 1개만 만들어지니 
  • for i in range(1, 10): dp[1][i] = 1 로 빠르게 해결 후
• n = 2부터 실행하게 해서 j = 0의 경우엔 갈 수있는 경로가 1밖에 없기에
  • dp[i-1][1] 로 이전 배열의 1번의 dp 값을 그대로 가져오기
• 마찬가지로 j = 9 또한 경로가 8밖에 없기에 
  • dp[i-1][8] 로 이전 배열의 8번의 dp 값을 그대로 가져오기
• 다른 수의 경우엔 위아래로 갈 수 있기에 두 개의 dp값을 더한 값을 누적하여 풀기

 

n = int(input())
dp = [[0]*10 for _ in range(n+1)]
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)