[백준] 11057 오르막 수

문제 설명

문제 링크

해당 문제에서 말하는 오르막 수란 수의 자리가 오름차순을 이루는 수를 말한다.
즉, 숫자를 문자열 S라고 가정했을 때, S[N] <= S[N+1]이 성립하는 수를 말한다.

문제를 살펴보면, 자리수에 따라 총 몇 개의 오르막 수가 있는지 구하는 것이 목표이다.

자리수가 늘어남에 따라 어떤 규칙이 있는지 확인해야 하며, 이를 통해 점화식을 세워야 한다. 특히, N의 최대값이 1000, 즉 길이가 1000인 수가 들어올 수 있기 때문에, 시간복잡도를 고려하여 동적계획법으로 푸는 것이 바람직하다.

문제 풀이

첫 접근은 일차원 배열의 개념으로 생각해보았다. 주어진 예제에 있는 55라는 숫자는 너무나 익숙한 수이기 때문에 (1부터 10까지의 수들의 합) 이를 기준으로 잡고 나머지 예제들의 답인 10과 220과 어떤 관계로 점화식을 세워야 할지 생각했는데, 오랜 고민 끝에 이렇게는 답이 나오지 않을 것 같았다.

그래서 2차원 배열을 이용하여 접근해보았다.
우선 자리수가 하나인 경우, 0부터 9까지의 수는 모두 오르막 수로 볼 수 있다.
즉, DP 테이블을 아래와 같이 표현할 수 있다.

N \ 1의자리	0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1	1

그렇다면 자리수(N)이 2인 경우를 확인해보자.
두자리 수의 경우, 1의자리가 0이면 오르막 수는 00 하나밖에 없다.
1의자리가 1이면 01, 11 두 개의 오르막 수가 있다. 이와 같이 채우면 다음과 같은 표가 나온다.

N \ 1의자리	0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9	10

패턴이 보이는 것도 같지만, 확실하게 하기 위해 어차피 문제에서 주어진 N = 3인 경우도 표현해보자.

N \ 1의자리	0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9	10
3	1	3	6	10	15	21	28	36	45	55

이렇게 보니 규칙이 더 명확해진다.

테이블을 dp로 정의하고, dp[i][j]는 i자리수의 j로 끝나는 오르막 수의 개수라고 정의하자.
dp[i][j]는 바로 직전 행 i-1에서 해당 열 j까지의 수들의 합임을 확인할 수 있다.

그렇다면, dp[i][j-1]은 직전 행 i-1에서 열 j-1까지의 수들의 합일테고, 여기에 간단하게 dp[i-1][j]를 더해주면 원하는 답이 구해진다.

점화식
dp[i][j] = dp[i][j-1] + dp[i-1][j]

코드

import sys

input = sys.stdin.readline

N = int(input())

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

for k in range(N + 1):
    dp[k][0] = 1

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

print(sum(dp[N]) % 10007)

---