[백준] 10844번(쉬운 계단 수)

백준 10844번

최종 제출 코드

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

dp[1] = [0,1,1,1,1,1,1,1,1,1]

for i in range(2, len(dp)):
  dp[i][0] = dp[i-1][1]
  dp[i][1] = dp[i-1][0] + dp[i-1][2]
  dp[i][2] = dp[i-1][1] + dp[i-1][3]
  dp[i][3] = dp[i-1][2] + dp[i-1][4]
  dp[i][4] = dp[i-1][3] + dp[i-1][5]
  dp[i][5] = dp[i-1][4] + dp[i-1][6]
  dp[i][6] = dp[i-1][5] + dp[i-1][7]
  dp[i][7] = dp[i-1][6] + dp[i-1][8]
  dp[i][8] = dp[i-1][7] + dp[i-1][9]
  dp[i][9] = dp[i-1][8]

n = int(input())

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

.
◼ n-1층에서 n층으로 올라오는 경우와 n+1층에서 n층으로 내려오는 경우의 수만 세면 됨