합 분해

문제

언어

  • JavaScript

문제 풀이 step 1

  • dp[k][n] = 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수
  • DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
  • N = 20, K = 2인 경우를 생각해보겠습니다. (dp[2][20])
  • 경우의 수를 생각해보겠습니다. (N === 20 이므로 0 ~ 20 해서 총 21개 입니다.)
    • 맨 뒤에 0 이 오는 경우의 수는 dp[1][20]입니다. (O + O + …)( === 20) + 0
    • 맨 뒤에 1 이 오는 경우의 수는 dp[1][19]입니다. (O + O + …)( === 19) + 1
    • …
    • 맨 뒤에 20 이 오는 경우의 수는 dp[1][0]입니다. (O + O + …)( === 0) + 20
  • dp[k][n] = dp[k - 1][n] + dp[k - 1][n - 1] + … + dp[k - 1][0]

문제 풀이 step 2

  • 점화식을 구할 수 있게 해준 발상은 아래와 같습니다.
  • 결국 K가 몇이 되던 정수 N을 만들때 사용하는 수는 0 ~ N 안에서 결정됩니다.
  • 그리고 문제에서 1 + 2 와 2 + 1 을 다른 경우로 생각했으니까, 앞에 어떻게 오든 맨 뒤에 1이 오는 경우, 2가 오는 경우, …, N이 오는 경우를 생각하게 되면서 점화식을 구하게 되었습니다.

후기

  • 다시 풀어보니 꼭 다시 풀어볼 문제였습니다.
  • 단순하고 딱딱하게만 생각하지말고, 유연하고 다양하게 생각하는 것이 필요한 것 같습니다.
    • 구체적으로 dp[][]의 괄호의 순서를 바꾸거나, 모든 경우의 수를 고려해보는 생각이 필요합니다.

소스 코드

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

const solution = (input) => {
	const MOD = 1000000000;
	const [N, K] = input[0].split(" ").map(Number);
	const dp = Array.from({length: K + 1}, () => []);

	// base
	for (let i = 0; i < N + 1; i++) {
		dp[0][i] = 0;
		dp[1][i] = 1;
	}

	for (let i = 2; i < K + 1; i++) {
		for (let j = 0; j < N + 1; j++) {
			let cnt = 0;

			for (let k = 0; k < j + 1; k++) {
				cnt += dp[i - 1][k];
			}

			dp[i][j] = cnt % MOD;
		}
	}

	return dp[K][N];
};

console.log(solution(input));