문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3
  • 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

예제

예제 입력 1

1
2
3
4
5
3
4
7
10

예제 출력 1

1
2
3
7
44
274

내 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map(Number);
const N = input.shift();

const DP = [0, 1, 2, 4];

input.forEach((num) => {
  for (let i = 4; i <= num; i++) {
    DP[i] = (DP[i - 3] + DP[i - 2] + DP[i - 1]) % 1000000009;
  }
  console.log(DP[num]);
});
  • 1을 1,2,3으로 만들 수 있는 경우의 수, 2를 1,2,3으로 만들 수 있는 경우의 수, 3을 1,2,3으로 만들 수 있는 경우의 수는 직접 구할 수 있어서 구하였다.
  • 4부터는 맨 마지막에 1,2,3이 오는 경우의 수를 나누어서 생각하였다.
    • 맨 마지막에 1이 오는 경우 ⇒ 1+1+1+1, 1+2+1, 2+1+1, 3+1 ⇒ DP[4-1]
    • 맨 마지막에 2가 오는 경우 ⇒ 1+1+2, 2+2 ⇒ DP[4-2]
    • 맨 마지막에 3이 오는 경우 ⇒ 1+3 ⇒ DP[4-3]

하지만 위와 같은 방법으로 하게되면 n이 1,000,000이 주어졌을 때, 반복문은 n-3회 진행하므로 시간초과가 난다. 심지어 테스트 케이스 수가 T개 주어지는 만큼 n-3회 반복해야 하므로 매우 오래걸릴 수도 있게된다.

즉, input 값 중에서 가장 큰 값으로 반복문 한번만 순회한 다음, 완성된 DP 배열에서 해당 값을 찾는 식으로 방법을 바꿨다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map(Number);
const N = input.shift();

function solution(n, arr) {
  if (n < 4) return arr[n - 1];

  for (let i = 4; i <= n; i++) {
    DP[i] = (DP[i - 3] + DP[i - 2] + DP[i - 1]) % 1000000009;
  }
  return arr;
}

const DP = [0, 1, 2, 4];
solution(Math.max(...input), DP);

input.forEach((num) => {
  console.log(DP[num]);
});