728x90
반응형
문제
https://www.acmicpc.net/problem/11057
풀이 방법
한창 DP 문제를 풀 때의 문제들을 올리고 있어서 아마 한동안은 DP문제들만 게시할 것 같다..문제를 간단하게 리뷰하면 오르막수는 수가의 자리가 오름차순으로 이루어진 수를 말한다. 이때, 같은 수인 경우에도 오름차순으로 생각한다.
예를들어 1123, 3456, 249 등의 수가 있다.
수의 자리수 N이 주어지면 이 오름차순인 N자리 수의 개수를 구하면 되는 문제다.
이 문제도 DP를 사용해서 풀이했다.
바로 직전의 문제와 동일하게 dp[N][10] 의 2차원 배열을 선언해주고, N은 몇자리 수인지, 그리고 뒤에 0~9는 마지막 자리라고 생각해줬다.
예를 들어 2135 인 숫자는 dp[4][5] 에 포함이 되어있을 것이다.
그래서 이제 dp[N][] 의 값들은 dp[N-1][] 에서 구해지기 때문에 반복문은 N-1까지 수행했다.
그리고 이제 뒷자리 수를 탐색하면서 오름차순으로 만들수 있는 다음 자리 수에 더해줬다.
예를 들어 dp[3][2]차례에서는 이제 2 다음에 2부터 9까지의 수가 와야지 오르막수를 만들 수 있다. 그러므로 이런 경우에는 dp[4][2] 부터 dp[4][9]까지의 배열 전부에 dp[3][2]의 값 + dp[4][j](j는 2부터 9)를 더해서 dp[4][j](j는 2부터 9)에 대입해준다.
dp값을 구하는 반복문이 끝나고 나면 이제 dp[N][]에 있는 모든 값들을 더해준다.
출력값을 10007로 나눈 나머지의 값을 출력해야하므로 혹시나 범위에 넘어갈 수 있으니 앞에서도, 더할때도, 출력할때도 10007로 미리미리 나눠서 넣어준다.
제출 코드
import java.io.*;
public class BJ_11057_오르막수 {
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];
for (int i = 0; i < 10; i++) {
dp[1][i] = 1;
}
for (int i = 1; i < N; i++) { //N-1번째 까지 실행
for (int j = 0; j < 10; j++) { //j는 맨 뒷자리
for (int k = j; k < 10; k++) { //뒤에 붙일 수 있는 수는 j부터 9까지 이므로
dp[i + 1][k] = (dp[i + 1][k] +dp[i][j])% 10007; //현재까지 만들 수 있는 자리수를 i+1자리의 뒷자리가 k인 경우에 더해주기
}
}
}
int sum = 0;
for (int i = 0; i < 10; i++) {
sum += (dp[N][i] % 10007);
}
System.out.println(sum % 10007);
}
}
728x90
반응형
'알고리즘 > BJ' 카테고리의 다른 글
[BJ] 백준 3052 나머지 (JAVA) (0) | 2022.03.24 |
---|---|
[BJ] 백준 2193 이친 수 (JAVA) (0) | 2022.03.21 |
[BJ] 백준 10844 쉬운 계단 수 (JAVA) (0) | 2022.03.17 |
[BJ] 백준 2116 주사위쌓기(JAVA) (0) | 2022.03.16 |
[BJ] 백준 11463 1로 만들기(JAVA) (0) | 2022.03.14 |