[백준알고리즘] 11057번: 오르막 수 -Python

[백준알고리즘] 11057번: 오르막 수 -Python

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

11057번: 오르막 수

수의 자릿수가 주어지면 인접한 수가 같거나 오름차 순을 만족하는 수의 갯수를 구해야 한다. 이 문제는 동적 계획법으로 해결이 가능하다.

 

이전에 풀었떤 10844 쉬운 계단 수 문제와 유사하다. 여기서는 0으로 시작할 수 있고 이전 수와 같아도 된다는 특징이 있다.

 

우선 초기 값으로 0~9까지 1로 채운 리스트를 하나 준비한다. 이 리스트에는 가장 오른쪽 값이 해당 인덱스일때 가능한 수의 갯수가 들어가있다. 즉 한 자리 숫자로 0~9까지 끝나게 되는 수는 모두 1가지 있으므로 이 값들을 초기값으로 설정한다.

 

다음은 두 자리 숫자를 생각해봐야 한다. 0으로 끝나기 위해서는? 이전 수도 0일 수 밖에 없으므로 new_nums[0] = nums[0]이다.

1로 끝나기 위해서는 이전 수에 0, 1이 올 수 있다. 그렇기 때문에 new_nums[1] = nums[1] + nums[0] = nums[1] + new_nums[0] 이다.

2로 끝나기 위해서는 이전 수에 0, 1, 2가 올 수 있기 때문에 new_nums[2] = nums[2] + nums[1] + nums[0] = nums[2] + new_nums[1]이 된다.

 

반복해서 풀다보면 점화식 new_nums[i] = new_nums[i - 1] + nums[i] 를 구할 수 있게 된다.

 

import sys

N = int(sys.stdin.readline())
nums = [1] * 10
mod = 10007

for _ in range(N-1):
    for i in range(1, 10):
        nums[i] = (nums[i] + nums[i-1]) % mod

sys.stdout.write(str(sum(nums) % mod))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다