백준 22.02.12. 10844번 - 쉬운 계단 수

n = int(input())

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

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)

• n자릿수의 경우의 수를 각 수(0~9)마다 저장하기위해 dp리스트를 만들었습니다.
• 규칙을 이끌어내기 위해 1자릿수의 정답들은 리스트에 지정해줍니다.
  • 반복을 통해서 초깃값을 지정했습니다.
• 표를 보면 규칙이 있습니다.
  • 0이 마지막에 오는 경우는 그 앞자리는 반드시 1입니다.
  • 9가 마지막에 오는경우 그 앞자리는 반드시 8입니다.
  • 표를 보면 알 수 있듯이 n자릿수를 구할 때 i번째 수의 경우의 수는 n-1자릿수의 i-1번째 수와 i+1번째 수의 경우의 수를 합한 것과 같습니다.
    • => dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
• 따라서 0과 9는 예외로 취급하여 따로 분기를 만들어주고 1~8범위에 들어가는 수들은 찾아낸 규칙을 적용시켜 구해줍니다.