[백준] 9095_1,2,3 더하기 (Javascript)

문제

BOJ9095_1,2,3 더하기

풀이

n을 1,2,3의 합으로 나타낼 수 있는 방법의 수를 구해야 한다. 그러기 위해 우선 n=1,2,3일때 1,2,3의 합으로 n을 나타낼 수 있는 방법의 수를 구해보자.
n=1일 경우

• 1

n=2일 경우

• 1+1
• 2

n=3일 경우

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

n이 1,2,3일 때 각각 1,2,4의 방법의 수를 갖는다.
이를 응용하여 n=4일 때의 방법의 수를 구해보자.

• 1+3

• 1+1+2

• 2+2

• 1+1+1+1

• 1+2+1

• 2+1+1

• 3+1

이런 식으로 n이 1이었을 때의 조합에 3을 더하고, 2였을 때의 조합에 2를 더하고, 3이었을 때의 조합에 1을 더함으로써 n=4일 때의 경우의 수가 7임을 알 수 있다.

이와 같은 방식으로 n=5일 때는 n이 2,3,4였을 때의 조합에 각각 3,2,1을 더해주면 된다.

이를 점화식으로 표현해보자면 아래와 같다.

dp[1] = 1, dp[2] = 2, dp[3] = 4
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

그리고 이를 바탕으로 코드로 구현하면 아래 코드가 된다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./LJH/input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n").map(Number);
input = input.slice(1);
let dp = {
    1: 1,
    2: 2,
    3: 4,
};
input.forEach((n) => {
    for (let i = 4; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }
    console.log(dp[n]);
});