[백준] 11057 오르막 수 (JavaScript)

https://www.acmicpc.net/problem/11057

문제 설명

• 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 문제
• 수는 0으로 시작할 수 있다.

예제 입력/출력

• 입력1

  1

• 출력1

  10

• 입력2

  2

• 출력2

  55

• 입력3

  3

• 출력3

  220

제약 조건

• $1 ≤ N ≤ 1,000$
• $0 ≤$ 각 자리 수 $≤ 9$

문제 풀이

접근1 브루트포스

• 길이가 N인 모든 숫자를 전부 생성한 뒤, 각 숫자가 오르막 수인지 검사하는 방식
  • 각 자리는 0 ~ 9
  • 총 경우의 수: $10^N$
• 최악의 경우 $10^{1000}$ 개의 숫자 생성이 필요하기 때문에 현실적으로 불가능

---

접근2 DP

길이 / 맨뒷자리 수	0	1	2	3	4	5	6	7	8	9	결과
1	1	1	1	1	1	1	1	1	1	1	10
2	10	9	8	7	6	5	4	3	2	1	55
3	55	45	36	28	21	15	10	6	3	1	220
4	220	165	120	84	56	35	20	10	4	1	715
…

• 위 표는 길이가 n이고, 맨 마지막 자리가 i인 오르막 수의 개수를 모두 정리한 것이다.
• 이 표가 어떻게 만들어지는지를 3단계로 나눠서 살펴보자.
  1. 길이가 1인 경우
     • 길이가 1이면 선택할 수 있는 숫자는 0 ~ 9 뿐이다.
     • 한 자리 수는 항상 오르막 수로 어떤 숫자가 오든 경우의 수는 1이다.
     • 이 값이 DP의 시작점(초기값) 이 된다.
  2. 길이가 2인 경우
     • 오르막 수이기 때문에 앞자리 숫자는 뒷자리 숫자보다 작아질 수 없다.
       • 마지막 자리가 0이면 → 앞자리는 0 ~ 9 모두 가능 → 10개
       • 마지막 자리가 1이면 → 앞자리는 1 ~ 9 가능 → 9개
       • …
       • 마지막 자리가 9이면 → 앞자리는 9만 가능 → 1개
  3. 같은 방식으로 계속 누적
     • 이 규칙은 길이가 늘어나도 절대 변하지 않는다.
     • 즉 길이가 n이고 마지막 숫자가 i인 경우의 수는 길이가 n-1이고 마지막 숫자가 i 이상인 모든 경우의 합이다.

1️⃣ DP 테이블 정의

dp[n][i]: 길이가 n인 오르막 수 중, n번째 자리에 숫자 i가 오는 경우의 수

• n: 수의 길이 ($1 ≤ n ≤ N$)
• i: 현재 자리의 숫자 ($0 ≤ i ≤ 9$)
• 수는 0으로 시작할 수 있음.

2️⃣ 초기값 설정

dp[1][i] = 1  (0 ≤ i ≤ 9)

• 길이가 1인 경우에는, 각 숫자 하나만 선택하면 되므로 모든 경우의 수는 1이다.

3️⃣ 점화식

dp[n][i] = dp[n-1][i] + dp[n-1][i+1] + ... + dp[n-1][9]

• 오르막 수의 조건상, 현재 자리에 i가 오려면 이전 자리에 오는 숫자는 i 이상이어야 한다.
  • 즉, 이전 자리 숫자는 i ~ 9
  • 해당 경우의 수를 모두 더한다.

4️⃣ 최종 결과 계산

answer = Σ dp[N][i]   (0 ≤ i ≤ 9)

• 길이가 N인 오르막 수의 총 개수는 마지막 자리에 올 수 있는 모든 숫자를 합한 값이다.

풀이 코드

DP

메모리: 9,984 kB
시간: 156 ms

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : `${__dirname}/input.txt`;
const input = fs.readFileSync(filePath).toString();

const N = Number(input);
const MOD = 10_007;

// dp[n][i] : n번째 자리에 i가 들어왔을 때 가능한 경우의 수
const dp = Array.from({ length: N + 1 }, () => Array(10).fill(0));

// DP 초기화
dp[1].fill(1);

// DP
for (let n = 2; n <= N; n++) {
  for (let i = 0; i <= 9; i++) {
    let sum = 0;
    for (let j = i; j <= 9; j++) {
      sum = (sum + dp[n - 1][j]) % MOD;
    }
    dp[n][i] += sum;
  }
}

// 결과
let answer = 0;
for (let i = 0; i <= 9; i++) {
  answer = (answer + dp[N][i]) % MOD;
}

console.log(answer);