백준 10844 파이썬 - 쉬운 계단 수 - 동적 계획법

백준 10844 파이썬

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

이번 문제는 계단 수를 구하는 문제이다. 계단 수는 "45656" 처럼 숫자의 자릿수 마다 하나 씩 줄고 늘어나는 수를 말한다. 0으로 시작할 수 없으며 90은 계단 수가 아니다. 이런 조건으로 아래와 같은 규칙이 만들어 진다.

• 0 다음에는 1만 올 수 있다.
• 9 다음에는 8만 올 수 있다.
• 나머지 숫자에 대해서는 앞뒤 모두 올 수 있다.

동적 계획법으로 숫자의 길이에 따라 만들 수 있는 숫자의 갯수를 저장하는데... 각 숫자의 끝자리를 기준으로 기억할 수 있는 메모이제이션 리스트를 생성해서 사용한다.

 

 

Python 풀이

import sys
read = sys.stdin.readline

N = int(read())
cache = [0,1,1,1,1,1,1,1,1,1]

for _ in range(N-1):
    temp = [0] * 10
    for n in range(10):
        if n-1 >= 0:
            temp[n-1] += cache[n]
        if n+1 <= 9:
            temp[n+1] += cache[n]
    cache = temp
print(sum(cache) % 1_000_000_000)

• 캐시의 초기 값은 숫자가 1자리일 경우의 값을 모두 입력해준다.
• 1자리인 경우는 정의했으므로 N-1 만큼 for문을 돌리고 임시 리스트를 만들어 다음 길이의 수를 구한다.
  • n-1 >= 0 : n이 1~9
  • n+1 <=9 : n이 0~8
  • n이 0인 경우 끝자리가 1인 숫자의 수를 1번 더한다.
  • n이 9인 경우 끝자리가 8인 숫자의 수를 1번 더한다.
  • 그외는 앞뒤의 수로 새로운 계단 수를 만들 수 있기 때문에 앞뒤 숫자의 수를 1번 씩 더한다.
• 문제의 조건에 따라 10^9를 나눠서 출력한다.