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

 

 

1. 문제설명

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

9095번: 1, 2, 3 더하기

 

 

2. 예제 입/출력

예제 입력	예제 출력
3 4 7 10	7 44 274

 

3. 문제 풀이

const fs = require("fs");

let input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map(Number);

let T = input[0];
for (let i = 1; i <= T; i++) {
  // 현재 값을 변수 n에 할당
  let n = input[i];

  // 0부터 n까지의 수를 1, 2, 3의 합으로 나타내는 방법의 수를 저장하는 배열
  // 배열은 0부터 시작하니까, n이 4일 경우 0 ~ 4까지 총 5개 요소 필요(n + 1)
  let dp = new Array(n + 1).fill(0);

  // 초기 상태: 0은 1가지 방법, 1은 1가지 방법, 2는 2가지 방법
  dp[0] = 1;
  dp[1] = 1;
  dp[2] = 2;

  // 3부터 n까지 1, 2, 3의 합으로 나타내는 방법의 수 계산해서 dp에 저장
  for (let j = 3; j <= n; j++) {
    dp[j] = dp[j - 1] + dp[j - 2] + dp[j - 3];
  }
  console.log(dp[n]);
}

 

dp는 중복 계산을 피하기 위해서 동적 계획법(Dynamic Programming)을 사용한 배열로,

각 인덱스가 정수를 나타내고 해당 인덱스를 1, 2, 3의 합으로 나타내는 방법의 수가 저장되며

dp[4]는 정수 4를 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 저장한다.

 

또한 dp 초기값은 0으로 채우고, dp[0]은 정수 0을 나타내는 방법, dp[1]은 정수 1을 나타내는 방법, dp[2]는 정수 2를 나타내는 방법(1 + 1, 2 = 2가지)으로 설정한다.

 

dp[3]부터는 이전 값을 활용해서 dp[2], dp[1], dp[0](2 + 1 + 1) = 4

dp[4]는 dp[3], dp[2], dp[1](4 + 2 + 1) = 7이 저장이 된다.