[python] 백준 10844번 문제풀이

백준 10844번 쉬운 계단 수 문제 풀이를 해보겠습니다.

출처 : 백준

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

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

출력

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

풀이

문제 설명: 동적 계획법을 이용해 계단 수를 구하는 문제

• 0으로 시작하는 수는 계단 수가 아니다
• 0 ~ 9 까지의 수가 계단에 들어갈 수 있다
• 계단이 i번째라면 i-1번째 계단의 수에 1을 뺀 값과 1을 더한 값이 들어 갈 수 있다
• 길이가 N이라면 길이가 N-1인 계단 수를 이용해 만들 수 있다
• 계단 수의 길이와 계단의 마지막 자리 수를 저장하고 개수를 출력하는 리스트를 만든다

점화식

• dp[2][1] = dp[1][0] + dp[1][2] 0 + 1 => 1
• dp[2][2] = dp[1][1] + dp[1][3] 1 + 1 => 2

• dp[2][9] = dp[1][8] + dp[1][10] 1 + 0 => 1

• dp[i][j] += dp[i-1][j+1] (j<9)
• dp[i][j] += dp[i-1][j-1] (j>0)

코드

import sys
input = sys.stdin.readline

def main():
    N = int(input().strip())

    dp = [[0]*10 for _ in range(N+1)]
    #dp[길이][마지막 자리수] 2차원 리스트 생성해 개수 저장

    for i in range(1,10) : 
        #길이가 1이면 들어갈 수 있는 숫자의 개수가 1
        dp[1][i] = 1

    #길이가 2이상일 때
    for i in range(2,N+1) :
        for j in range(10) : #마지막 자리수 (0~9)
            if j>0: #숫자가 0보다 클 때 j-1 가능
                dp[i][j] += dp[i-1][j-1]  
            if j<9: #숫자가 9보다 작을 때 j+1 가능
                dp[i][j] += dp[i-1][j+1]
            dp[i][j] = dp[i][j] % 1000000000 
            #1000000000으로 나눈 나머지를 저장
    
    result = sum(dp[N])%1000000000 
    #dp[N]을 모두 더하고 1000000000으로 나눈 나머지 출력
    print(result)

main()