백준 15990 - 1, 2, 3 더하기 5

문제 설명

 

 

=> DP 문제이다. 

=> 기존 문제아 달리 이차원 배열로 하여 문제를 해결하여야 한다. 

 

 

• dp[i][j] : i를 1,2,3의 합으로 나타내는 방법의 수, j : 마지막에 사용한 수 
• dp[i][1] : 바로 전에 사용할 수 있는 수는 2,3
• dp[i][2] : 바로 전에 사용할 수 있는 수는 1,3
• dp[i][3] : 바로 전에 사용할 수 있는 수는 1,2

 

 if (n - 1 >= 0) {
            dp[n][1] = (dp[n - 1][2] + dp[n - 1][3]) % mod;
        }
        if (n - 2 >= 0) {
            dp[n][2] = (dp[n - 2][1] + dp[n - 2][3]) % mod;
        }
        if (n - 3 >= 0) {
            dp[n][3] = (dp[n - 3][1] + dp[n - 3][2]) % mod;

위의 알고리즘을 통해 DP를 진행할 수 있다. 

 

 

 

 

 

 

 

 

초기화의 경우

    dp[1][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1; //dp initialization

 

=> 위와 같은 방법으로 초기화를 해주어야 중복을 피할 수 있다. 

 

 

 

 

 

 

<전체 코드>

#include <iostream>
#include <algorithm>



using namespace std;

long long dp[100001][4]={0};
const int mod = 1000000009;
const int Max = 100000;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int N;
    cin>> N;
    
    dp[1][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1; //dp initialization
    
    for (int n = 4; n <= Max; n++)
    {
        if (n - 1 >= 0) {
            dp[n][1] = (dp[n - 1][2] + dp[n - 1][3]) % mod;
        }
        if (n - 2 >= 0) {
            dp[n][2] = (dp[n - 2][1] + dp[n - 2][3]) % mod;
        }
        if (n - 3 >= 0) {
            dp[n][3] = (dp[n - 3][1] + dp[n - 3][2]) % mod;
        }
    }
    int val;
    
    
    
    while(N>0)
    {
        cin >> val;
        cout << (dp[val][1] + dp[val][2] + dp[val][3]) % mod<<'\n';
        
        N--;
    }
}

 

 

 

 

 

실행 화면 

 

실행화면 2