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

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

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

1, 2, 3의 합을 통해 수를 만들 때, 경우의 수가 몇개가 나오는지 구하는 문제입니다.

 

같은 개수를 사용해도 위치가 다르다면 다른 경우로 봅니다.

예를 들어, 1 + 1 + 2와 2 + 1 + 1은 서로 다른 경우입니다.

 

1, 2, 3을 통해 만드는 것이기에 이전의 수들로 부터 +1, +2, +3을 한다면 수를 만들 수 있습니다.

 

만약, 7이라는 수를 만들려고 할 때, 6에 +1을 하면 됩니다. 그렇다는 것은 6의 경우의 수에 + 1을 더하면 된다는 것임으로

7은 6의 경우의 수를 모두 더하면 됩니다. 이 뿐만 아니라 같은 논리를 통해, 4, 5의 경우의 수도 모두 더해주면 됩니다.

 

이를 점화식으로 만들면,

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

이 됩니다.

 

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

#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];

void solve(){
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for(int i = 4; i <= N; i++){
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        dp[i] %= Div;
    }
    cout << dp[N] << "\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;
}

 

 

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