[BOJ 15989] 1, 2, 3 더하기 4

문제

1, 2, 3 더하기 4

https://www.acmicpc.net/problem/15989

 

 

풀이

설명

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제입니다.

 

DP를 사용해 해결할 수 있습니다.

 

dp[i]는 i를 1, 2, 3의 합으로 나타내는 방법의 수입니다.

dp[0] = 1로 초기화 해줍니다.

 

1, 2, 3을 num으로 나타낸다면

dp[i] = dp[i] + dp[i - num]입니다.

 

예시 코드

function solution() {
  const T = +input();
  const n = 10000;
  const dp = Array(n + 1).fill(0);
  const answer = [];
  dp[0] = 1;

  for (let i = 1; i <= 3; i++) {
    for (let j = i; j <= n; j++) {
      dp[j] += dp[j - i];
    }
  }

  for (let i = 0; i < T; i++) {
    const num = +input();
    answer.push(dp[num]);
  }

  return answer.join("\n");
}