[Algorithm/JS] 백준 9095번 1, 2, 3 더하기

🔗 문제 바로가기 (opens new window)

Question

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

Input

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

Output

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

Example

Input

3
4
7
10

Output

7
44
274

Solution

알고리즘: DP

정수 n 이 1 일 때 조합 (1개)

1

정수 n 이 2일 때 조합 (2개)

1 + 1 2

정수 n이 3일 때 조합 (4개)

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

그렇다면 정수 n 이 4일 때는? (7개)

정수 3일 때 : 1 + 1 + 1 + 1
정수 3일 때 : 1 + 1 + 2
정수 3일 때 : 1 + 2 + 1
정수 2일 때 : 2 + 1 + 1
정수 2일 때 : 2 + 2
정수 3일 때 : 3 + 1
정수 1일 때 : 1 + 3

이를 DP 식으로 풀어내면,

• 3일 때 조합이 4개 → DP[N-1]
• 2일 때 조합이 2개 → DP[N-2]
• 1일때 조합이 1개 → DP[N-3]

DP[N] = DP[N-1] + DP[N-2] + DP[N-3] 으로 나타낼 수 있다.

const fs = require('fs');
const [t, ...input] = fs
  .readFileSync('dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .map(Number);

const dp = new Array(12).fill(0);
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;

input.map((v) => {
  for (let i = 4; i <= v; i++) {
    dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
  }
  console.log(dp[v]);
});