동호의 블로그

www.acmicpc.net

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

문제 설명

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 문제

수는 0으로 시작할 수 있다.

예제 입력/출력

입력1

출력1

입력2

출력2

입력3

출력3

제약 조건

각 자리 수

문제 풀이

`접근1` 브루트포스

길이가 N인 모든 숫자를 전부 생성한 뒤, 각 숫자가 오르막 수인지 검사하는 방식

각 자리는 0 ~ 9
총 경우의 수:

최악의 경우 개의 숫자 생성이 필요하기 때문에 현실적으로 불가능

`접근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이면 선택할 수 있는 숫자는 0 ~ 9 뿐이다.

한 자리 수는 항상 오르막 수로 어떤 숫자가 오든 경우의 수는 1이다.

이 값이 DP의 시작점(초기값) 이 된다.

길이가 2인 경우

오르막 수이기 때문에 앞자리 숫자는 뒷자리 숫자보다 작아질 수 없다.

마지막 자리가 0이면 → 앞자리는 0 ~ 9 모두 가능 → 10개
마지막 자리가 1이면 → 앞자리는 1 ~ 9 가능 → 9개
…
마지막 자리가 9이면 → 앞자리는 9만 가능 → 1개

같은 방식으로 계속 누적

이 규칙은 길이가 늘어나도 절대 변하지 않는다.

즉 길이가 n이고 마지막 숫자가 i인 경우의 수는 길이가 n-1이고 마지막 숫자가 i 이상인 모든 경우의 합이다.

1️⃣ DP 테이블 정의


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

n: 수의 길이 ()

i: 현재 자리의 숫자 ()

수는 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
해당 경우의 수를 모두 더한다.

❗

문제 조건에 따라 반드시 더한값은 10007로 나눈 나머지를 사용한다.

4️⃣ 최종 결과 계산


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

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

❗

문제 조건에 따라 반드시 결과값은 10007로 나눈 나머지를 사용한다.

풀이 코드

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);

문제 설명

예제 입력/출력

제약 조건

문제 풀이

접근1 브루트포스

접근2 DP

풀이 코드

DP

`접근1` 브루트포스

`접근2` DP