공부 136일차: 백준 11057번 오르막 수 자바 java
11057 오르막 수
https://www.acmicpc.net/problem/11057
11057번: 오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수
www.acmicpc.net
백준 11057번 문제 오르막 수
문제
과정 생각해보기
이렇게 구해보면 규칙을 발견할 수 있다
표로 정리한 규칙은 다음과 같다
| n\i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | (0~9) 10 |
(1~9) 9 |
(2~9) 8 |
(3~9) 7 |
(4~9) 6 |
(5~9) 5 |
(6~9) 4 |
(7~9) 3 |
(8~9) 2 |
(9) 1 |
| 3 | (0~9) 55 |
(1~9) 45 |
(2~9) 36 |
(3~9) 28 |
(4~9) 21 |
(5~9) 15 |
(6~9) 10 |
(7~9) 6 |
(8~9) 3 |
(9) 1 |
따라서
dp[n][0] = dp[n-1][0] + dp[n-1][1] + dp[n-1][2] + dp[n-1][3] + dp[n-1][4] + dp[n-1][5] + dp[n-1][6] + dp[n-1][7] + dp[n-1][8]+ dp[n-1][9]
dp[n][1] = dp[n-1][1] + dp[n-1][2] + dp[n-1][3] + dp[n-1][4] + dp[n-1][5] + dp[n-1][6] + dp[n-1][7] + dp[n-1][8]+ dp[n-1][9]
dp[n][2] = dp[n-1][2] + dp[n-1][3] + dp[n-1][4] + dp[n-1][5] + dp[n-1][6] + dp[n-1][7] + dp[n-1][8]+ dp[n-1][9]
dp[n][3] = dp[n-1][3] + dp[n-1][4] + dp[n-1][5] + dp[n-1][6] + dp[n-1][7] + dp[n-1][8]+ dp[n-1][9]
dp[n][4] = dp[n-1][4] + dp[n-1][5] + dp[n-1][6] + dp[n-1][7] + dp[n-1][8]+ dp[n-1][9]
dp[n][5] = dp[n-1][5] + dp[n-1][6] + dp[n-1][7] + dp[n-1][8]+ dp[n-1][9]
dp[n][6] = dp[n-1][6] + dp[n-1][7] + dp[n-1][8]+ dp[n-1][9]
dp[n][7] = dp[n-1][7] + dp[n-1][8]+ dp[n-1][9]
dp[n][8] = dp[n-1][8]+ dp[n-1][9]
dp[n][9] = dp[n-1][9]
라는 식을 구할 수 있다
이때 우리가 구해야 하는 수는 dp[n][0] + … + dp[n][9] 이다
정답 인정 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
import java.io.*;
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());
final int MOD = 10_007;
int[][] dp = new int[n+1][10];
for(int i = 0; i < 10; i++) {
// 1자리일 때 0~9로 끝나는 숫자는 모두 1개씩
dp[1][i] = 1;
}
for(int i = 2; i < n+1; i++) {
for(int j = 0; j < 10; j++) {
for(int k = j; k < 10; k++) {
// 오버플로우를 막기 위한 나머지 연산
dp[i][j] += (dp[i-1][k]) % MOD;
}
}
}
int sum = 0;
for(int i = 0; i < 10; i++) {
sum += dp[n][i];
}
// 오버플로우를 막기 위한 나머지 연산
System.out.println(sum%MOD);
}
}
|
cs |
과정 설명은 다소 복잡해보이지만 코드로는 어렵지 않다