1, 2, 3 더하기 5

문제

언어

  • JavaScript

문제 풀이 step 1

  • dp[n] = 정수 n이 주어졌을 때, 1, 2, 3의 합으로 나타내는 방법의 수
  • 모든 방법은 1과 2와 3의 합으로 이루어져있습니다는 사실을 이용합니다.
  • DP의 특징 중 하나인 작은 문제의 해답으로부터 큰 문제의 해답을 구할 수 있다를 응용합니다.
  • 각 방법을 나열했을 때 모양은 ‘1 + 2 + 3’ 혹은 ‘3 + 2 + 1’ 혹은 ‘1 + 3 + 2’과 같을 것입니다.
  • 이 때 맨 뒤를 주목합니다. 맨 뒤의 수는 1 또는 2 또는 3일 수밖에 없습니다.
  • 모든 경우의 수는 3가지일 수 밖에 없습니다. 1과 2와 3의 합으로만 이루어져 있기 때문입니다. (또한 같은 수를 두번 이상 연속해서 사용할 수 없습니다.)
    1. 뒤에 1이 오는 경우 dp[n][1] = dp[n-1][2] + dp[n-1][3]
    2. 뒤에 2가 오는 경우 dp[n][2] = dp[n-2][1] + dp[n-2][3]
    3. 뒤에 3이 오는 경우 dp[n][3] = dp[n-3][1] + dp[n-3][2]
  • 위와 같은 경우를 만들어낼 수 있습니다.

소스 코드

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

const solution = (input) => {
	const T = parseInt(input[0]);
	const arr = input.slice(1, T + 1).map(Number);
	const n = Math.max(...arr);

	const MOD = 1000000009;
	const dp = Array.from({length: n + 1}, () => []);

	dp[1][1] = 1;
	dp[1][2] = 0;
	dp[1][3] = 0;

	dp[2][1] = 0;
	dp[2][2] = 1;
	dp[2][3] = 0;

	dp[3][1] = 1;
	dp[3][2] = 1;
	dp[3][3] = 1;

	for (let i = 4; i < n + 1; i++) {
		dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % MOD;
		dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % MOD;
		dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % MOD;
	}

	let res = "";
	for (let i = 0; i < T; i++) {
		const index = arr[i];
		res += `${(dp[index][1] + dp[index][2] + dp[index][3]) % MOD}\n`;
	}

	return res;
};

console.log(solution(input));