1, 2, 3 더하기 4

문제

언어

  • JavaScript

순서도

  1. 점화식을 정의하고, 그에 맞게 dp 배열 생성하기
  2. dp 배열의 base 값 정의
  3. 점화식과 base 값을 이용해서 dp 배열 채우기
  4. dp[n][1] + dp[n][2] + dp[n][3] 출력하기

문제 풀이 step 1

  • 정수 4 를 1, 2, 3 의 합으로 나타내는 방법은 총 4 가지가 있습니다. 합을 나타낼 때는 수를 1 개 이상 사용해야 합니다.
  • 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 칩니다.
    • 1 + 1 + 1 + 1
    • 2 + 1 + 1 (1 + 1 + 2, 1 + 2 + 1)
    • 2 + 2
    • 1 + 3 (3 + 1)
  • 정수 n 이 주어졌을 때, n 을 1, 2, 3 의 합으로 타나내는 방법의 수를 구하는 문제입니다.

문제 풀이 step 2

  • dp[n][k] = 정수 n 을 합으로 나타내는 방법 중 맨 뒤에 k 가 오는 방법의 수
    • 본 문제에서는 1, 2, 3 의 합으로 나타내기 때문에 dp[n][1], dp[n][2], dp[n][3] 이렇게 총 3 가지가 있겠습니다.
  • DP의 특징인 “작은 문제의 해답으로부터 큰 문제의 해답을 찾는다”를 이용합니다.
  • 점화식은 다음과 같습니다.
    • dp[n][1] = dp[n - 1][1];
      • n - 1 을 만드는 방법 중에서 맨 뒤에 1 이 오는 방법들을 가지고 뒤에 1 을 추가한 것입니다.
    • dp[n][2] = dp[n - 2][1] + dp[n - 2][2];
      • n - 2 를 만드는 방법 중에서 맨 뒤에 1, 2 가 오는 방법들을 가지고 뒤에 2 를 추가한 것입니다.
    • dp[n][3] = dp[n - 3][1] + dp[n - 3][2] + dp[n - 3][3];
      • n - 3 을 만드는 방법 중에서 맨 뒤에 1, 2, 3 이 오는 방법들을 가지고 뒤에 3 을 추가한 것입니다.
  • 점화식을 위와 같이 작성한 이유는 다음과 같습니다.
    • “합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다” 라고 되어 있습니다.
    • 그렇기 때문에 (2 + 1 + 1), (1 + 2 + 1), (1 + 1 + 2) 이 3 방법 모두 하나의 방법이 됩니다.
    • 점화식처럼 뒤에 숫자를 추가할 때, 추가할 숫자 이하의 수로 이루어진 방법들에 수를 추가하면 오름차순으로 방법들을 셀 수 있습니다.
    • 즉, (1 + 1 + 2) 과 같이 오름차순으로 정렬된 경우만 고려하게 되는 것입니다.
    • 이러면 순서가 뒤바뀐 방법들을 중복해서 고려할 필요가 없게 됩니다.
  • base 값은 다음과 같습니다.
    • dp[1][1] = 1
    • dp[2][1] = dp[2][2] = 1
    • dp[3][1] = dp[3][2] = dp[3][3] = 1
  • base 값을 토대로 점화식을 이용해서 dp 배열을 채워가면 됩니다.
  • dp 배열을 모두 채웠으면, n 을 만드는 모든 방법의 수인 dp[n][1] + dp[n][2] + dp[n][3] 을 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 오름차순 정렬을 통해서 각 방법의 수의 순서를 강요함으로써 수의 순서가 다른 방법들은 고려하지 않는 방법이 되게 좋았던 것 같습니다.

소스 코드

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

const solution = (input) => {
	const n = Number(input[0]);
	const arr = input.slice(1).map(Number);

	const dp = Array.from({length: 10001}, () => Array(4).fill(0));

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

	// bottom-up
	for (let i = 4; i < 10001; i++) {
		dp[i][1] = 1;
		dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
		dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3];
	}

	return arr.map((v) => dp[v].reduce((ac, v) => ac + v)).join("\n");
};

console.log(solution(input));