오르막 수

문제

백준 11057번 - 오르막 수

언어

JavaScript

문제 풀이 step 1

dp[n][0] = 길이가 1이며 맨 뒤의 수가 0인 오르막 수의 개수
dp[n][1] = 길이가 1이며 맨 뒤의 수가 1인 오르막 수의 개수
…
dp[n][9] = 길이가 1이며 맨 뒤의 수가 9인 오르막 수의 개수
DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
앞의 n - 1 만큼의 과정은 완성되어 있다고 가정하고, n번째를 생각해보겠습니다.
오르막 수가 되기 위해서는 인접한 수가 같거나 오름차순이어야 합니다.
- 따라서 맨 뒤에 0이 오는 경우는 바로 이전에 인접한 수가 0 일 수 밖에 없습니다.
  - dp[n][0] = dp[n - 1][0]
- 맨 뒤에 1이 오는 경우는 바로 이전에 인접한 수가 0 or 1 일 수 밖에 없습니다.
  - dp[n][1] = dp[n - 1][0] + dp[n - 1][1]
- …
- 맨 뒤에 9가 오는 경우는 바로 이전에 인접한 수가 0 or 1 or … or 9 로 모든 수가 가능합니다.
  - dp[n][9] = dp[n - 1][0] + dp[n - 1][1] + … + dp[n - 1][9]
10 가지의 경우의 수를 모두 더한 값이 길이가 n 인 오르막 수의 개수입니다.

소스 코드

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const solution = (input) => {
	const MOD = 10007;
	const N = parseInt(input[0]);

	const dp = Array.from({length: N + 1}, () => []);
	dp[1] = Array.from({length: 10}, (v, i) => 1);

	for (let i = 2; i < N + 1; i++) {
		dp[i] = Array.from({length: 10}, () => 0);
		for (let j = 0; j < 10; j++) {
			for (let k = 0; k < j + 1; k++) {
				dp[i][j] += dp[i - 1][k];
				dp[i][j] %= MOD;
			}
		}
	}

	return dp[N].reduce((ac, v) => (ac + v) % MOD);
};

console.log(solution(input));

다른 방식의 문제 풀이 step 1

이전 단계에서 구한 값을 이용해서 반복을 줄일 수 있습니다.
예를 들어 dp[n][6]의 경우,
dp[n][6]은 dp[n -1][0] + dp[n - 1][1] + … + dp[n - 1][5] + dp[n - 1][6] 입니다.
그리고 dp[n][5]는 dp[n - 1][0] + dp[n - 1][1] + … dp[n - 1][5] 입니다.
방정식에 의해서,
dp[n][6] = dp[n][5] + dp[n - 1][6] 입니다.
이를 공식으로 바꾸면, dp[n][k] = dp[n][k - 1] + dp[n - 1][k] 입니다.
이를 이용하면 내부 반복문을 줄일 수 있습니다.

소스 코드

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const solution = (input) => {
	const MOD = 10007;
	const N = parseInt(input[0]);

	const dp = Array.from({length: N + 1}, () => []);
	dp[1] = Array.from({length: 10}, (v, i) => 1);

	for (let i = 2; i < N + 1; i++) {
		dp[i] = Array.from({length: 10}, () => 0);

		// 맨 뒤가 0인 오르막수는 무조건 1개이다.
		dp[i][0] = 1;

		// 원래라면 dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j] 이다.
		// dp[i-1][0] + ... + dp[i-1][j-1] 은 dp[i][j-1]과 같다.
		// 내부 반복문 제거
		for (let j = 1; j < 10; j++) {
			dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
			dp[i][j] %= MOD;
		}
	}

	return dp[N].reduce((ac, v) => (ac + v) % MOD);
};

console.log(solution(input));