[백준 10844번] 파이썬 - 쉬운 계단 수

백준 10844 - 쉬운 계단 수

시간 제한 1초, 메모리 제한 256MB

# 조건

• 45656이란 수를 보자.
• 이 수는 인접한 모든 자리의 차이가 1이다.
• 이런 수를 계단 수라고 한다.
• N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자.
• 0으로 시작하는 수는 계단수가 아니다.

입력

• 첫째 줄에 N이 주어진다.
• N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

• 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

# 접근 방법

• 2차원 리스트를 활용한 DP로 풀어주었다.
• 문제의 핵심은 제일 뒤의 숫자가 어떤 숫자인지에 따라 DP의 값을 누적해나가는 것이다.
• 1자리 수의 경우 0을 제외한 1~9에 1을 기입해준다.
• 2자리 수의 경우
  • 뒷 자리가 0인 경우 10의 자리에 올 수 있는 것은 1자리 수의 1과 같다. 즉 DP[2][0] = dp[1][1]
  • 1~8의 경우 1 큰 수와, 1 작은 수의 경우의 수를 합친 것과 같다.
    • dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
  • 9의 경우 1자리 작은 8의 경우의 수와 같다.
    • dp[2][9] = dp[1][8]
• 이런 식으로 갱신해 나가면 된다.
• 사진은 아래 블로그 참고..!

https://cotak.tistory.com/12

import sys  
input = sys.stdin.readline  

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 1 <= j <= 8:  
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]  

        else:  
            dp[i][j] = dp[i-1][8]  

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