[Python] 백준 - 11057 오르막 수

출처: 백준 온라인 저지
https://www.acmicpc.net/problem/11057

---

정석적인 풀이

from sys import stdin


n = int(stdin.readline().strip())

# n X 10의 행렬 만들기
uphill = [[0] * 10 for _ in range(n + 1)]

# 0~9로 시작하는 한자리 숫자의 개수 = 1
uphill[1] = [1] * 10

for i in range(2, n + 1):
    # 0으로 끝나는 i자리 숫자의 개수 = 1
    uphill[i][0] = 1

    for j in range(10):
        uphill[i][j] = uphill[i - 1][j] + uphill[i][j - 1]

print(sum(uphill[n]) % 10007)

b로 끝나는 a자리 오르막 수의 개수를 uphill[a][b]라고 하자. 예를 들어, 6으로 끝나는 4자리 오르막 수의 개수는 uphill[4][6]이다. 4자리 오르막 수가 6으로 끝나려면, 앞의 3자리 수가 6 이하의 수로 끝나는 오르막 수여야 한다.

따라서 uphill[4][6] = uphill[3][0] + uphill[3][1] + ... + uphill[3][6]이 성립한다.

하지만 uphill[a][b]의 값을 구하기 위해 매번 이렇게 값들을 다 더할 필요는 없다.

uphill[a][n] = uphill[a - 1][0] + ... + uphill[a - 1][n]이므로,
uphill[a][n - 1] = uphill[a - 1][0] + ... + uphill[a - 1][n - 1]이다.

따라서 uphill[a][n]은 uphill[a][n - 1]과 uphill[a - 1][n]의 합으로 나타낼 수 있다.

uphill[a][b] = uphill[a - 1][b] + uphill[a][b - 1]

a가 1인 경우와 b가 0인 경우는 초기값으로 설정해주어야 한다.

a가 1인 경우 : b로 끝나는 1자리 수는 b밖에 없으므로 uphill[1][b]는 1이다.
b가 0인 경우 : 0으로 끝나는 a자리 수는 1개이므로 uphill[a][0]은 1이다.

그런데 사실 이 문제는 훨씬 간단하게 풀 수도 있다.

이산수학을 활용한 풀이

import math

n = int(input())
print(math.comb(9 + n, n) % 10007)

이산수학의 관점에서 생각해보면, 사실 오르막 수는 10개의 수(0~9) 중에서 중복을 허용한 조합과 같다.

n개 중 r개의 조합을 고르는 경우의 수를 $nCr$이라고 할 때,

n개 중 중복을 허용하여 r개의 조합을 고르는 경우의 수는 $n+r-1Cr$이다.

n자리의 오르막 수는 10개의 숫자 중 중복을 허용하여 n개의 조합을 고르는 것이므로, 그 수는 $10+n-1Cn$이다. 이 수식을 조합의 개수를 구해주는 math 모듈의 comb() 함수로 구현하면 위처럼 코드 한 줄로 답을 구할 수 있다.

---

순열과 조합이 코딩 테스트 문제 풀이에 유용한 경우들이 종종 있는 것 같아서, 코딩 테스트에 필요한 순열과 조합 지식을 정리해보았다.

코딩 테스트를 위한 최소한의 순열과 조합