[백준][#9095] 1, 2, 3 더하기 - JavaScript

문제 설명

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

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

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

[예제 입력1]

3
4
7
10

[예제 출력1]

7
44
274

풀이

n = 4 일 때,
1로 시작했을 때는 3의 값을 조합하면 되는데 n=3일 때가 3을 조합할수 있는 모든 경우의 수이기 때문에 이를 이용하면 1로 시작했을 때 4를 만들 수 있는 경우의 수를 구할 수 있다.

마찬가지로 2로 시작했을 때는 2의 값을 조합하면 되는데 이는 이전의 값을 이용하면 되고 3로 시작했을 때도 1의 값을 조합해야하는데 이것 또한 이전의 값을 이용하는 관계를 가지기 때문에 배열로 값을 저장하면 불필요한 계산을 줄일 수 있다.

이러한 방식으로 더 큰 값 n = 10일 경우 dp[10] = dp[10 - 1] + dp[10 - 2] + dp[10 - 3]의 방식을 이용하면 구할 수 있다.

최종 코드

const solution = (N, data) => {
    let answer = '';
    const dp = [0, 1, 2, 4];

    for (let i = 0; i < N; i += 1) {
        for (let j = 4; j <= data[i]; j += 1) {
            dp[j] = dp[j - 1] + dp[j - 2] + dp[j - 3];
        }
        const idx = data[i];

        if (i < N - 1) answer += `${dp[idx]}\n`;
        else answer += `${dp[idx]}`;
    }

    console.log(answer);
};

const fs = require('fs');

const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input[0];
const data = [];
for (let i = 1; i <= N; i += 1) {
    data.push(+input[i]);
}

solution(N, data);