백준 11057번 오르막 수 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 11057 오르막 수

11057 오르막 수

출처

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

11057번: 오르막 수

자릿수가 오름차순으로 증가하는 수를 오르막 수라고 하고 이전이나 다음 자릿수는 같은 크기를 가져도 오르막 수이다.

점화식을 찾아 문제를 풀이해야 했고 그 과정이 생각보다 오래 걸렸다. N과 끝으로 오는 수를 기준으로 점화식을 세워야 한다.

 

알고리즘 분류

• 다이내믹 프로그래밍

---

소스코드

 

import sys
input = sys.stdin.readline

n = int(input())
dp = [1] * 10

for i in range(n-1):
    for j in range(1, 10):
        dp[j] += dp[j-1]

print(sum(dp) % 10007)

---

풀이

어떠한 수가 오름차순 즉 이전수보다 크거나 같다면 오르막 수라고 부를 수 있다.

자릿수 n이 1일 때 0~9의 수가 올 수 있는 경우의 수를 가진 이전 리스트를 활용하여 n이 커질 때 n-1의 리스트를 활용하여 규칙을 찾을 수 있다.

N과 끝의 수를 기준으로 표로 작성하자면

N ∖ 끝의 수	0	1	2	3	4	~	9
1	1	1	1	1	1	~	1
2	1	2	3	4	5	~	10
3	1	3	6	10	15	~	55

이 표를 통해 끝의 수 i는 N-1일 때 i에 i-1을 더하면 끝의 수가 i일 때 만들 수 있는 오르막 수의 개수를 구할 수 있다.

끝의 수 0~9까지 dp를 저장하는 리스트를 하나만 작성해도 이전 N-1만 사용하기 때문에 괜찮다.

즉 이전 dp에 i-1만 더해주면 새로운 N의 끝의 수들을 업데이트할 수 있다.

문제에서는 자릿수에 따른 오르막 수의 개수를 구하길 원하므로 이 dp를 더하고 10007로 나누어 출력하면 된다.

---

풀이 결과