[백준] 9095 - 1, 2, 3 더하기(javascript)

문제

9095번: 1, 2, 3 더하기

나의 풀이

2가지 방식으로 풀이가 가능하다.

 

dp [i] = dp [i - 3] + dp [i - 2] + dp [i - 1] 임을 이용한 dp 방법,

0부터 1,2,3을 더하면서 경우의 수를 모두 매칭하는 재귀 방법

DP

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

const caseLEN = Number(input[0]);
const dp = {
  0: 0,
  1: 1,
  2: 2,
  3: 4,
};
let max = Math.max(...input);

for (let i = 4; i <= max; i++) {
  dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
}

let answer = "";
for (let i = 1; i <= caseLEN; i++) {
  answer += dp[input[i]] + "\n";
}
console.log(answer.trim());

 

재귀

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

let answer = 0;
let goal = 0;
let result = "";

function add(sum) {
  if (sum > goal) return;
  if (sum == goal) {
    answer++;
    return;
  }

  add(sum + 1);
  add(sum + 2);
  add(sum + 3);
}

for (let i = 1; i <= input[0]; i++) {
  answer = 0;
  goal = input[i];
  add(0);
  result += answer + "\n";
}

console.log(result.trim());

 

자세한 이론적인 설명은 아래 링크에서 확인하시면 됩니다. (저도 이걸 보고 배웠어요 ㅎ..)

백준 9095번 : 1, 2, 3 더하기