백준 11057번 - 오르막 수

오르막 수 문제 바로 가기

풀이 날짜: 2026-01-12

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline

n = int(input())
dp = list([0]*10 for _ in range(n+1))
dp[1] = [1] * 10

for i in range(2,n+1):
    for j in range(10):
        if j==0:
            dp[i][j] = 1
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(sum(dp[n]) % 10007)

문제 접근

이 문제는 길이가n인 “오르막 수(자리수가 줄어들지 않는 수)”의 개수를 구하는 문제라서, 한 자리씩 늘려가며 경우의 수를 누적하는 방식이 자연스럽다.
어떤 수가 오르막이 되려면 마지막 자릿값이 정해졌을 때 그 이전 자리들이 만들 수 있는 경우의 수로 계산할 수 있기 때문에, “길이”와 “마지막 숫자”를 상태로 두는 DP로 풀 수 있다.

DP 정의

dp[i][j] = 길이가 i이고 마지막 숫자가 j인 오르막 수의 개수.

헷갈렸던 점 정리

초기값이 왜 dp[1] = [1]*10 인지

길이가 1인 수는 0~9 각각이 그 자체로 오르막 수이기 때문에, 마지막 숫자가 0이든 9든 가능한 수는 딱 1개씩 존재한다.
그래서 dp[1][0..9] = 1 이 되고, 코드로는 dp[1] = [1] * 10이 되는 것이다.
반대로 dp[0]은 길이가 0이기 때문에 (= 아무 숫자도 없는 상태), 문제에서 실제 숫자로 쓰이지 않고, 이 풀이에서는 굳이 사용할 필요가 없기 때문에 초기 시작을 dp[1]로 했다.

최종 답이 sum(dp[n]) 인 이유

우리가 구하고 싶은 건 길이 n인 오르막 수의 “전체 개수”다. 그런데 DP는 “마지막 숫자별 개수”로 나뉘어 있으니, 길이 n에서 마지막 숫자가 0~9인 경우를 모두 더하면 전체가 된다. 그래서 답은 sum(dp[n])이고, 마지막에 문제 조건에 따라 10007로 나눈 나머지를 출력한다.

Vienna sausage