1. 문제 설명
숫자의 자릿수가 주어질 때, 해당 자릿수를 가지고 만들 수 있는 오르막수의 개수를 구하라.
오르막수?
숫자의 가장 왼쪽부터 시작해 오른쪽으로 갈수록 자릿수의 크기가 작아지지 않는 수를 오르막수라고 한다. 다시 말해,
1234, 2569 등이 오르막수이다.
작아지지 않으면 된다고 하였으므로,
1111, 1119도 오르막수가 된다.
2. 접근 방식
KEYWORD: DP
자릿수가 1000의 자리까지 주어진다. 중복 순열로 문제를 푼다면, O(1000!) 이니까, 당연히 문제를 풀지 못한다. 따라서 해당 문제는 DP를 사용해야 한다.
그렇다면, DP는 어떻게 생각해야 할까?
2차원 배열로 DP를 만들어보겠다. 세로는 자릿수, 가로는 맨왼쪽의 숫자가 무엇으로 시작하는지 나타내는 것이다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 3 | 55 | 45 | 36 | 29 | 23 | 18 | 14 | 11 | 9 | 8 |
| 4 | 220 | --- | --- | --- | --- | --- | --- | --- | --- | --- |
자릿수가 1개일 때는 당연히 맨 왼쪽 start 숫자 하나만 쓰일 것이고, 각 숫자마다 경우의 수가 1만 존재할 것이다.
자릿수가 2개일 경우, 0으로 시작하면 2번째 자리가 0~9까지 10개 가능하므로, 10개, 같은 방식으로 9,8,7,6,5 ... 이렇게 갈 것이다.
자릿수가 3개일 때를 보자. 0으로 왼쪽 start 하면 가능한 오르막수의 개수가 55개이다. 이를 어떻게 구했을까?
DP에서 가장 중요한 것은 이전에 구한 값들을 어떻게 재활용할 것인가?이다.
다음은, 2번째 자릿수까지의 오르막수를 나타낸 모습이다. 이제 이것들을 오른쪽으로 밀고, 왼쪽에 새로운 숫자를 넣는다고 가정해보자.
만약 맨왼쪽의 수가 0이라면 2번~3번까지는 어디까지 활용할 수 있을까?
2~3번째는 자릿수가 2개일 때 구했던 모든 경우의 수들을 다 쓸 수 있다. 따라서 dp[3] [0] = (10+9+8+...) = 55 이다. 나머지 수들은 몇 가지만 예시로 보여주겠다.
이렇게 되면, 3자릿수까지 나올 수 있는 모든 오르막수의 개수를 구하라고 한다면 dp[4] [0]은 3자릿수에서 나올 수 있는 모든 경우의 수의 합이므로, 답은 dp[4] [0]을 그대로 출력하면 된다.
모듈러 연산 쓰는 법
그 다음 고민해야할 것이 모듈러 연산 사용이다. 문제에서 답은, 나올 수 있는 오르막 수의 개수를 10007로 나눈 수를 출력하라고 했다. 모듈러 연산은 다음과 같다.
(A + B) % N = (A%N + B%N)%N증명은 다음과 같다.
A = q1*N + r1
B = q2*N + r2 // 라고 하면,
(A+B)%N = (q1*N + r1 + q2*N + r2)%N // 이때, %N을 풀어서 구하면 q1*N과 q2*N은 나머지가 0이므로 사라짐.
//따라서
(q1*N +r1 + q2*N +r2)%N = (r1 + r2)%N
r1 = A%N, r2 = B%N // 이므로
(A+B)%N = (r1 + r2)%N = (A%N + B%N)%N해당 모듈러 연산은 덧셈 뿐만 아니라 뺄셈, 곱셈에서도 같은 원리로 증명되므로 사용 가능하다.
위의 원리를 우리의 문제에 적용해야하는 이유는, N자릿수에서 가능한 오르막 수의 개수를 구하는 도중에, 부분합이 이미 int의 최대값을 넘어버리면, 오버플로우가 되어서 값이 이상해지기 때문이다. 이를 해결하기 위해, 문제에서도 10007이라는 수로 나누라고 배려한 것이다.
따라서 우리는 dp에서 오르막 개수를 구할 때 각 값마다 10007로 나눠준다. 따라서 점화식은
dp[N][j] = S(dp[N-1][k]%10007);
// k는 j보다 작은 수 , S()는 dp[N-1][0]%10007 ~ dp[N-1][k]%10007까지의 합 3. 코드 분석
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int [][] dp = new int[N+1][10];
Arrays.fill(dp[0], 1);
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 10; j++) {
for (int k = j; k < 10; k++) {
dp[i][j] += (dp[i-1][k]%10007);
}
dp[i][j] %= 10007;
}
}
System.out.println(dp[N][0]);
}
}
