문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

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

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

입력

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

출력

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

예제

예제 입력 1

1
2
3
4
5
3
4
7
10

예제 출력 1

1
2
3
3
9
27

내 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 시간 초과
const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const T = +input.shift();
const nums = input.map(Number);
const N = Math.max(...nums);

// DP[n][k] 는 n을 만들 때 끝의 자리수가 k로 끝나는 경우의 수를 나타낸다. (k = 1,2,3)
const DP = Array.from({ length: N + 1 }, () => new Array(4).fill(0));

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;

nums.forEach((num) => {
  for (let i = 4; i <= num; i++) {
    for (let j = 1; j <= 3; j++) {
      if (j === 1) {
        DP[i][j] = (DP[i - j][2] + DP[i - j][3]) % 1000000009;
      }
      if (j === 2) {
        DP[i][j] = (DP[i - j][1] + DP[i - j][3]) % 1000000009;
      }
      if (j === 3) {
        DP[i][j] = (DP[i - j][1] + DP[i - j][2]) % 1000000009;
      }
    }
  }
  console.log(DP[num].reduce((acc, cur) => (acc + cur) % 1000000009, 0));
});
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const T = +input.shift();
const nums = input.map(Number);
const N = Math.max(...nums);

// DP[n][k] 는 n을 만들 때 끝의 자리수가 k로 끝나는 경우의 수를 나타낸다. (k = 1,2,3)
const DP = Array.from({ length: N + 1 }, () => new Array(4).fill(0));

DP[1][1] = 1; // 1
DP[1][2] = 0;
DP[1][3] = 0;
DP[2][1] = 0;
DP[2][2] = 1; // 2
DP[2][3] = 0;
DP[3][1] = 1; // 2+1
DP[3][2] = 1; // 1+2
DP[3][3] = 1; // 3

for (let i = 4; i <= N; i++) {
  for (let j = 1; j <= 3; j++) {
    for (let k = 1; k <= 3; k++) {
      if (j === k) continue;
      DP[i][j] += DP[i - j][k] % 1000000009;
    }
  }
}

nums.forEach((num) => {
  console.log(DP[num].reduce((acc, cur) => (acc + cur) % 1000000009, 0));
});
  1. DP[n][k]는 n 을 만들 때, 끝의 자리수가 k로 끝나는 경우의 수를 나타낸다. (k = 1,2,3)
  2. j가 1이면 k는 1이 아니여야만 가능하다. 왜냐하면 연속해서 올 수 없기 때문이다.
  3. DP 저장을 해줄 때에도 1000000009을 나눠주고 합한 것도 나눠줘야하는 이유를 모르겠다.