Skip to content
logo
Padosum Wiki
Github
On this page

백준 11057 JavaScript

수정하기
문서 생성 2022-02-01 15:17:29 최근 수정 2022-02-01 15:23:39
On this page

문제

백준 11057

풀이

백준 10844와 비슷하고 생각한다.
문제를 풀기 위해 N이 주어질 때 나오는 오르막 수를 확인해보자. 

N = 1
0, 1, 2, 3, 4, 5, 6, 7, 8, 9


N = 2
00, 01, 02, 03, 04, 05, 06, 07, 08, 09
11, 12, 13, 14, 15, 16, 17, 18, 19
22, 23, 24, 25, 26, 27, 28, 29
...
99


N = 3
000, 001, 002, 003, 004, 005, 006, 007, 008, 009
011, 012, 013, 014, 015, 016, 017, 018, 019
111, 112, 113, 114, 115, 116, 117, 118, 119
122, 123, 124, 125, 126, 127, 128, 129
...
....

손가락이 아프니 이쯤하도록 한다.
N=1인 경우에는 0으로 시작해 9까지 한 자리수들이 나오고,
N=2인 부분을 잘 생각해 보자.
2자리인 숫자가 만약 2로 끝난다면 (ex, 02, 12, 22, 32, 42... )
오르막 수가 되기위해 십의 자리수는 0, 1, 2 중 하나여야만 한다.
그럼 숫자를 합하면 02, 12, 22가 만들어지므로 총 세 개가 된다.
따라서 다음 식이 성립이 된다.

DP[N][1의 자리수] = DP[N-1][0] + ... + DP[N-1][1의 자리수]

아래 코드에 DP[N]의 합은 N 자리일 때 오르막 수의 합이 된다.

const readFileSyncPath = require('path').basename(__filename).replace(/js$/, 'txt');
// const readFileSyncPath = '/dev/stdin';
const input = require('fs').readFileSync(readFileSyncPath).toString().trim().split("\n");


const N = Number(input[0]);


// DP[N][마지막 자리수]
const DP = new Array(N + 1).fill(0).map(() => Array(10).fill(0));
const MOD = 10007;


// 길이가 1인 오르막 수 -> 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
for (let i = 0; i <= 9; i++){
  DP[1][i] = 1;
}


// 길이가 i일 때 j(0~9)로 끝나는 경우 구하기
// x2 -> x: 0 또는 1 또는 2
// x3 -> x: 0 또는 1 또는 2 또는 3 
// ex) 길이 2인 경우 2로 끝나는 오르막 수는 
// 앞 자리가 0, 1, 2 만 올 수 있다.  
// -> 즉, 길이가 1(i-1, 2-1)일 때 0, 1, 2인 수의 합 구하기
// DP[2][2] = DP[1][0] + DP[1][1] + DP[1][2]
for (let i = 2; i <= N; i++) {
  for (let j = 0; j <= 9; j++) {
    for (let k = j; k >= 0; k--) {
      DP[i][j] += (DP[i - 1][k]) % MOD;
    }
  }
}


let answer = 0;
DP[N].forEach((v, i) => {
  answer += v;
});


console.log(answer % MOD);

LINKS TO THIS PAGE