백준 15989 - 1, 2, 3 더하기 4(C++)

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

15989번: 1, 2, 3 더하기 4

2차원 다이나믹으로 풀 수 있는 문제였습니다.

1, 2, 3을 더함으로써 X라는 수를 만들 수 있는 경우의 수를 구하는 문제입니다.

 

중복된 경우를 없애는 방법은 오름차순으로서 경우를 관리하는 것입니다.

 

예를 들어, 1 + 1 + 2와 2 + 1 + 1을 오름차순으로 바꾸면 같은 경우가 됩니다.

 

모든 수의 합 경우를 저장할 수는 없음으로 배열을 사용해 저장할 것입니다.

 

[X][1~3]을 만들어

[X][1] -> 수의 합이 1로 끝

[X][2] -> 수의 합이 2로 끝

[X][3] -> 수의 합이 3으로 끝

 

따라서 마지막에 2를 더해야할 경우, [X-2][1] + [X][2]의 경우를 더해주면 됩니다.

 

 

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

#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][1] = dp[i-1][1];
        dp[i][2] = dp[i-2][1] + dp[i-2][2];
        if(i >= 3){
            dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3];
        }
    }
    cout << dp[N][1] + dp[N][2] + dp[N][3] << "\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;
}

 

 

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