해당 포스팅은 백준 11057번 오르막 수 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.
문제
1. 문제 설명
-
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.
-
[예시]
- 2234와 3678, 11119는 오르막 수이다.
- 2232, 3676, 91111은 오르막 수가 아니다.
-
수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하라.
-
수는 0으로 시작할 수 있다.
입력
첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.
출력
첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.
풀이
1. 로직
3자리 수 ___의 경우, 각 자리 수는 이전 자리 수의 STATE에 따라 들어갈 수 있는 수가 정해진다. 따라서 해당 문제는 DP로 해결할 수 있다.
자세한 로직은 예제를 통해 설명하겠다.
2. 로직
N = 3일 때 가능한 오르막 수의 개수를 구해보자.
앞서 말했듯 각 자리수는 이전 수의 STATE에 따라 들어갈 수 있는 숫자가 정해진다.
따라서 N=1부터 부분합을 구해보자.
[N =1]경우의 수 10가지- 한 자리 수이므로 들어갈 수 있는 경우는 0~9로 총 10가지이다.
- 0~9의 경우를 각각 1개의 경우의 수라고 따지자.
- DP에 N=1일 때를 DP[0]으로 저장하자.
DP[0] = [1,1,1,1,1,1,1,1,1,1]
[N =2]경우의 수 55가지-
십의 자리 수는 일의 자리 수의 값에 따라 들어갈 수 있는 수가 정해진다.
-
0 + 0~9 (10가지)
1 + 1~9 (9가지)
2 + 2~9 (8가지)
...
8 + 8~9 (2가지)
9 + 9 (1가지)
-
DP에 N=2일 때를 DP[1]으로 저장하자.
DP[1] = [10,9,8,7,6,5,4,3,2,1]
-
-
[N =3]경우의 수 220가지-
백의 자리 수는 이전 자리 수의 값에 따라 들어갈 수 있는 수가 정해진다.
-
0 + 00~99 (55가지)
1 + 11~99 (45가지)
2 + 22~99 (36가지)
...
8 + 88~99 (3가지)
9 + 99 (1가지) -
N = 3일 때 DP[2] = [55,45,36,28,21,15,10,6,3,1] 이다.
N = 2일 때 DP[1] = [10,9,8,7,6,5,4,3,2,1]이다.
해당 케이스를 보면DP[2][0] = DP[2][1] + DP[1][0]임을 확인할 수 있다.그 이유는
DP[2][0] = 0 + 00~99 // 55
DP[2][1] = 0 + 11~99 // 45
DP[1][0] = 0 + 0~9 // 10인데, DP[2][1]은 이전 수가 00~09인 케이스, 즉 DP[1][0]일 때가 제외되기 때문이다!
-
DP에 N=3일 때를 DP[2]으로 저장하자.
DP[2] = [55,45,36,28,21,15,10,6,3,1]
-
3. 점화식
점화식
DP[i][j] = DP[i][j+1] + DP[i-1][j]
전체 코드
const input = require('fs').readFileSync('/dev/stdin').toString();
const N = Number(input);
const DP = new Array(N+1);
for (let i = 0; i < DP.length; i++) {
DP[i] = new Array(10).fill(1);
}
for (let i = 1; i <= N; i++) {
for (let j = 8; j >= 0; j--) {
DP[i][j] = (DP[i][j+1] + DP[i-1][j]) % 10007;
}
}
console.log(DP[N][0]);