백준 10844 파이썬
https://www.acmicpc.net/problem/10844
10844번: 쉬운 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
이번 문제는 계단 수를 구하는 문제이다. 계단 수는 "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를 나눠서 출력한다.
댓글0