요즘 몸 상태가 좋지 않다. 그래서 쉬운 문제만 풀면서 요즘 자주 올리지 못한 풀이들을 올려볼까 한다.

BOJ 11057 - 오르막 수 링크
(2022.10.13 기준 S1)

문제

오르막 수는 수의 자리가 오름차순을 이루는 수이다.
수의 길이 N이 주어졌을 때, 오르막 수의 개수를 출력

알고리즘

수의 자리마다 다음 자리에 올 수 있는 수가 정해져 있으므로, 첫째 자리부터 경우의 수를 구해나가는 전형적인 Bottom-Up DP 문제라 할 수 있다.

풀이

일단 첫째 자리에는 0부터 9까지 하나씩 올 수 있다.
그럼 만약 첫째 자리가 5였으면 둘째 자리에는 5, 6, 7, 8, 9가 올 수 있다.
그럼 만약 둘째 자리가 7이면? 셋째 자리에는 7, 8, 9가 올 수 있다.

한 자리에는 숫자 하나씩 올 수 있다.
그리고 다음 자리의 숫자에는 직전 자리 숫자가 같거나 작은 모든 경우의 수가 더해지는 것이다.

이를 dp로 나타내 보자.
먼저 dp를 가로는 0 ~ 9, 세로는 수의 길이만큼 0으로 초기화하여 만들어 주자.
그리고 첫째 자리에는 0부터 9까지 하나씩 올 수 있으므로 1로 만들어 주고, 둘째 자리부터 dp를 채워나가면 된다.
만약 둘째 자리가 9인 경우의 수는? 첫째 자리가 0~9인 경우의 수들을 둘째 자리가 9인 경우의 수에 더해주면 되는 것이다.

for k in range(10):
	# 둘째 자리가 9인 경우의 수 += 첫째 자리가 0~9인 경우의 수 % 10007
	dp[1][9] += dp[0][k] % 10007

이런 방식으로 전부 채워서
마지막에는 dp[N-1]의 합을 10007로 나눈 나머지를 출력하면 된다.

풀이

N = int(input()) # 수의 길이
dp = [[0] * 10 for _ in range(N)] # 가로는 자리의 숫자 (0~9), 세로는 수의 자리
for i in range(10): # 첫번째 자리는 0부터 9까지 하나씩 올 수 있다.
    dp[0][i] = 1
# 둘째 자리부터 끝 자리까지 dp를 채워나간다.
for i in range(1, N):
    for j in range(10): # 0 ~ 9
        for k in range(j + 1): # 채우려는 숫자보다 같거나 작은 직전 자리의 숫자들의 경우의 수를 더하자.
            dp[i][j] += dp[i - 1][k] % 10007
print(sum(dp[N - 1]) % 10007) # 끝 자리의 경우의 수를 합하여 10007로 나눈 나머지를 출력

여담

정말 간단하면서도 기초적이고 교육적인 Bottom-up DP 문제였다.