백준[node.js] > 9095번 1, 2, 3 더하기

문제

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

 

풀이

dp로 푼 문제풀이이다. 이 풀이가 최적화된 풀이이고 밑에 보면 dfs로도 푼 문제가 있다. 

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

input = input.map((n) => Number(n));

for (let i = 1; i <= input.length - 1; ++i) {
    let target = input[i];

    let dp = new Array(target + 1).fill(0);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;

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

    console.log(dp[target]);
}

 

 

처음에 dfs로 접근했는데 그럴 필요가 없었다. 참고차 남겨둔다. 

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


input = input.map((n) => Number(n));

for (let i = 1; i <= input.length - 1; ++i) {
    let target = input[i];
    let answer = 0;
    let dfs = (sum) => {
        if (sum === target) {
            answer += 1;
            return;
        }

        for (let j = 1; j <= 3; ++j) {
            if (sum + j > target) {
                continue;
            }
            dfs(sum + j);
        }
    };
    dfs(0);
    console.log(answer);
}