백준 15990 - 1, 2, 3 더하기 5(C++)

문제 링크입니다. https://www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

2차원 배열을 이용한 Dp로 풀 수 있는 문제입니다.

1, 2, 3을 통해 수를 만드는 경우의 수를 구하는 문제입니다.

 

수를 만들 때, 같은 수가 2번이상 중복되면 안됩니다.

 

따라서 수를 만들 때 마지막으로 더한 수를 저장해줘야합니다.

-> 이를 2차원 배열을 통해 만들었습니다.

 

[X][1~3]은 X의 수를 만들 때, 1~3의 수로 끝났다는 의미입니다.

 

따라서 K라는 수를 만들 수 있는 경우는

[K][1] = [K-1][2] + [K][3]

[K][2] = [K-2][1] + [K-2][3]

[K][3] = [K-3][1] + [K-3][2]

-> [K][1] + [K][2] + [K][3]이 K를 만들 수 있는 경우의 수가 됩니다.

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#define Div 1000000009

using namespace std;

int test_case;
int N;
long long dp[1000001][4];

void solve(){
    dp[0][1] = 1;
    dp[1][1] = 1;
    for(int i = 2; i <= N; i++){
        dp[i][2] = dp[i-2][1] + dp[i-2][3];
        dp[i][1] = dp[i-1][2] + dp[i-1][3];
        if(i >= 3){
            dp[i][3] = dp[i-3][1] + dp[i-3][2];
        }
        dp[i][1] %= Div;
        dp[i][2] %= Div;
        dp[i][3] %= Div;
    }
    cout << (dp[N][1] + dp[N][2] + dp[N][3]) % Div << "\n";
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> test_case;
    for(int i = 1; i <= test_case; i++){
        cin >> N;
        solve();
    }
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.