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

문제

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

15988번: 1, 2, 3 더하기 3

---

문제 풀이

 해당 문제의 예시 입/출력을 보자. 4, 7, 10과 같은 작은 수가 나오더라도 이에 수 십배의 경우의 수가 나온다. n의 최댓값이 1,000,000인 것을 감안하면 완전 탐색은 불가능하다.

 

 문제를 조금 더 분석해보자. 식으로 나타낼 수 있는 숫자는 1, 2, 3이다. 나타내야 하는 수를 k라 할 때, k를 나타내기 위해서는 k보다 작은 수에서 1,2,3을 더하면 된다.

 즉 k를 1,2,3으로 나타 낼 수 있는 방법 k-1 +1, k - 2 + 2, k - 3 + 3이다.

해당 문제의 점화식

 

이 때 k -1, k -2 , k -3를 메모이제이션을 해두어 덧셈 연산으로 값을 구할 수 있도록 한다.

 

---

풀이 코드

const fs = require('fs');
const stdin = (process.platform === 'linux'? fs.readFileSync('/dev/stdin').toString() :
`3
4
7
10`).split('\n');

const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();


function solution(){
    const answer = [];
    const data = [];
    let memo = [0,1,2,4];
    const N = Number(input())
    for(let i = 0; i < N; i++){
        const tempData = Number(input());
        data.push(tempData);
    }
    var num = Math.max(...data);
    for(let j=4; j<=num; j++){
        memo[j] = (memo[j-1] + memo[j-2] + memo[j-3]) % 1000000009;
    }

    for(let i=0; i<N; i++){
        console.log(memo[data[i]]);
    }



}

solution();