문제

정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력

3
4
7
10

예제 출력

4
8
14

내가 했던 풀이 방법

1. 입력받은 n 중 가장 큰 값을 max에 저장한다.
2. max+1 크기의 dp 배열을 생성하고 각 요소에 배열의 크기가 4이고 0으로 채워진 배열로 초기화한다.
3. dp[i][1]은 i를 만들 수 있는 수의 합 중에서 가장 큰 값이 1인 경우 개수이고, dp[i][2]는 i를 만들 수 있는 수의 합 중에서 가장 큰 값이 2인 경우 개수이다. 이렇게 하는 이유는 같은 조합에서 순서만 다르다면 같은 경우로 취급하기 때문이다. 2+1+1, 1+1+2, 1+2+1 모두 하나로 취급한다. 이를 오름차순으로 정렬하면 1+1+2이기 때문에 얘를 개수로 취급해줄 것이다.
4. dp[1]~dp[3]까지의 경우를 저장해두고 i를 4부터 시작해서 max까지의 경우를 찾아준다. dp[i][1], dp[i][2], dp[i][3]의 합이 i를 만들 수 있는 모든 경우가 될 것이다.
5. dp[i][1]는 가장 큰 수가 1이므로 무조건 1만 포함되기 때문에 dp[i-1][1]의 값만 더해주면 된다. dp[i][2]는 가장 큰 수가 2이므로 dp[i-2] 중에 가장 큰 수가 1 또는 2인 경우를 더해주면 된다. 마지막으로 dp[i][3]도 같은 방법으로 dp[i-3]에서 가장 큰 수가 1, 2, 3인 경우를 더해주면 된다.

코드

const fs = require('fs');
let [T, ...n] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

T = Number(T);
n = n.map(Number);
let max = Math.max(...n);

let dp = Array.from({ length: max + 1 }, () => Array(4).fill(0));
dp[1][1] = 1;
dp[2][1] = 1;
dp[2][2] = 1;
dp[3][1] = 1;
dp[3][2] = 1;
dp[3][3] = 1;

for (let i = 4; i <= max; i++) {
  dp[i][1] = 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];
}

let answer = '';
for (let i = 0; i < T; i++) {
  let sum = 0;
  for (let j = 1; j <= 3; j++) {
    sum += dp[n[i]][j];
  }
  answer += sum + '\n';
}

console.log(answer.trim());

회고

2차원 배열까지도 떠올리긴 했는데 정렬을 하자니 해당 경우를 요소로 담는 건 비효율적일 것 같아서 아니겠지 했는데 정렬을 직접해서 저장해주지 않고도 정렬한 경우를 체크할 수 있다는 걸 생각해내지 못했다. 조금만 더 생각했다면 떠올렸을 것 같은데... 이 유형 문제도 다양하니까 여러번 풀고 기억해두어야 겠다.