백준 11057 오르막 수 - node.js

해당 포스팅은 백준 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]);