- 2688번 문제 : 완전히 같은 문제이고, 단지 N이 여러개 입력되는 것 뿐이다.
문제 이해
오르막 수는 가장 왼쪽 수부터 오름차순을 이루는 수이다.
이 때 같은 수가 붙어 있어도 오름차순이라고 생각하고, 수는 0으로 시작할 수 있다.
N자리 수 중 오름차순의 개수를 구하는 문제이다.
문제 풀이
N자리 수를 만들 수 있는 방법은 N-1자리 수에서 수를 하나 더 추가시키는 방법밖에 존재하지 않는다.(N-2자리수에서 2개를 추가하는 것은, N-1자리 + 1 + 1개 수를 포함하는 것이므로 N-1자리에서 1개를 추가하는 것과 동일)
이 때, (N-1) 자리 수에서 가장 마지막 자리에 수를 추가한다고 생각하자. 이 때 총 10가지 경우의 수가 존재할 것이다.
-
추가할 수가 0인 경우 : (N-1)자리 수의 가장 끝 자리 수가 0
-
추가할 수가 1인 경우 : (N-1)자리 수의 가장 끝 자리 수가 0, 1
-
추가할 수가 2인 경우 : (N-1) 자리 수의 가장 끝 자리 수가 0,1,2
....
- 추가할 수가 9인 경우 : (N-1) 자리 수의 가장 끝 자리 수가 0,1,2,3,4,5,6,7,8,9
위 경우의 수를 보면 추가할 수가 K인 경우는 (N-1) 자리 수의 가장 끝 자리 수가 K이하이다.
먼저 (N-1) 자리 수의 가장 끝 자리 수에 대한 값을 저장해야 하는 것이므로 DP 배열을 N*10 배열을 만들어 DP를 통해 문제를 풀기로 했다.
조금 더 심화적으로 생각해보자.
추가할 수가 K인 경우의 수는 가장 끝 자리 수가 K 이하인 경우의 수를 모두 더한 것이다.
추가할 수가 K-1인 경우의 수는 가장 끝 자리 수가 K-1이하인 경우의 수를 모두 더한 것이다.
즉, K인 경우의 수는 K-1을 추가한 경우의 수에서 (N-1)의 가장 끝자리가 K였던 경우만 더하면 되는 것이다.
코드
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N;
static int[][] dp_arr;
// dp_arr[i][j] : i번째 자리 수 중 가장 마지막 수가 j인 오르막수 개수
static void dp() {
for(int i =0;i<10;i++) {
dp_arr[1][i] = 1;
}
for(int i = 2;i<=N;i++) {
dp_arr[i][0] = 1;
for(int j =1;j<10;j++) {
dp_arr[i][j] = (dp_arr[i][j-1]+dp_arr[i-1][j])%10007;
/*
마지막에 추가할 수는 j이다.
즉, dp_arr[i-1][0] ~ dp_arr[i-1][j]를 모두 더해주면 된다.
((N-1)자리의 수 중 가장 마지막 수가 j 이하인 오르막수 개수를
모두 더해야 하므로)
dp_arr[i-1][0] ~ dp_arr[i-1][j-1] = dp_arr[i][j]임을
알고 있다.
또한 dp_arr[i][j]는 이미 구해져 있을 것이므로
dp_arr[i][j-1] + dp_arr[i-1][j]를 통해
dp_arr[i][j]를 구한다.
*/
}
}
}
public static void main(String[] args) throws IOException {
FastReader sc = new FastReader();
N = sc.nextInt();
dp_arr = new int[N+1][10];
dp();
int ans = 0;
for(int i =0;i<10;i++) {
ans+=dp_arr[N][i];
ans = ans%10007;
}
System.out.println(ans);
}
static class FastReader // 빠른 입력을 위한 클래스
}결과
- 2번째 줄 틀렸습니다 : 정답을 10007로 나눠줘야 하는데, 이 과정을 수행하지 않아 틀렸다.
