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

 

생각하기

20을 나타내는 방법의 수 = 4를 나타내는 방법의 수 x 16을 나타내는 방법의 수

 

각 숫자 나타내는 방법의 수 구하는 방법 = 백트레킹?

 

하짐나 DP로 풀어야 하는 문제이기 때문에 DP적으로 생각!

 

dp[num] = dp[num-1] + dp[num-2] + dp[num-3]

      마지막에 각 단계에서 부족했던 숫자들만 더해서 값을 뽑을 수 있다

      1을 구하는 방법에서 2을 더하는 방법 

      2를 구하는 방법에서 1을 더하는 방법

 

이미 구해 놓은 값들을 통해 구해낸다

 

* 각 숫자 때마다 dp값을 도출하기

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;
#define endl '\n'
#define DIV 1000000009

long T, input;
long dp[1000010];
int cnt;

void calculate(int num) {
    if(num<=3)
        return;
    if(dp[num-1]==0)    
        calculate(num-1);
    else if(dp[num-2]==0)
        calculate(num-2);
    else if(dp[num-3]==0)
        calculate(num-3);

    dp[num] = (dp[num-1]+dp[num-2]+dp[num-3])%DIV;
    
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> T;
    long* numbers = new long[T];
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for (int i = 0; i < T; i++) {
        cin >> input;
        numbers[i] = input;
    }
    for(int i=0; i<T; i++){
        calculate(numbers[i]);
        cout<<dp[numbers[i]]<<endl;
    }
    
}

* 한번에 모든 dp들을 저장해서 값을 추출하기

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;
#define endl '\n'
#define DIV 1000000009

long T, input;
long dp[1000010];


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> T;
    long* numbers = new long[T];
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for(int i=0; i<T; i++){
        cin>>input;
        numbers[i]=input;
    }
    for(int i=4; i<=1000000; i++){
        dp[i] = (dp[i-1]+dp[i-2]+dp[i-3])%DIV;
    }
    for(int i=0; i<T; i++){
        cout<<dp[numbers[i]]<<endl;
    }
}