[백준] 9095 1, 2, 3 더하기 Node.js

문제

정수 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은 양수이며 11보다 작다.

출력

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

예제 입력 1

3
4
7
10

예제 출력 1

7
44
274

---

문제풀이

💡문제풀이 과정

👉🏻 규칙을 찾기 위해서 직접 조합을 만들어 본다.

• n = 1 일 때: 1개
  • 1
• n = 2 일 때: 2개
  • 1 + 1
  • 2
• n = 3 일 때: 4개
  • 1 + 1 + 1
  • 2 + 1
  • 1 + 2
  • 3
• n = 4 일 때: 7개
  • n = 3 일 때 가능했던 조합에서 추가 (4개)
    • 1 + 1 + 1 + 1
    • 1 + 2 + 1
    • 2 + 1 + 1
    • 3 + 1
  • n = 2 일 때 가능했던 조합에서 추가 (2개)
    • 1 + 1 + 2
    • 2 + 2
  • n = 1 일 때 가능했던 조합에서 추가 (1개)
    • 1 + 3

👉🏻 위에서 n = 4 일 때의 규칙을 살펴보면 n이 3, 2, 1 일 때의 조합에서 각각 +1, +2, +3을 더했을 뿐이다.

👉🏻 즉, n = 4 일 때 ⇒ (n = 3 일 때의 조합 개수) + (n = 2일 때의 조합 개수) + (n = 1 일 때의 조합 개수)이다.

👉🏻 따라서, arr[n] = arr[n-1] + arr[n-2] + arr[n-3]

✅ 답안

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n').map(Number);
const tc = input.shift();
const arr = [0, 1, 2, 4]; // 1, 2, 3 일 때의 조합의 개수를 배열에 저장

for (let i = 0; i < tc; i++) {
  const n = input.shift();

  // n이 될 때까지 arr의 뒷부분에 조합 개수 추가
  for (let j = 4; j <= n; j++) {
    arr[j] = arr[j - 1] + arr[j - 2] + arr[j - 3];
  }
  console.log(arr[n]);
}