[백준 16195번] 1, 2, 3 더하기 9 (C++)

문제링크 : https://www.acmicpc.net/problem/16195

16195번: 1, 2, 3 더하기 9

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, n, m, dp[1001][1001];
const int MOD = 1000000009;

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

    cin >> T;
    dp[1][1] = dp[2][1] = dp[3][1] = 1; //1, 2, 3에 대해 1개씩 사용한 경우

    for(int i=2; i<1001; i++) //갯수
    {
        for(int j=1; j<1001; j++) //목표 값
        {
            for(int k=1; k<4; k++) //1, 2, 3
            {
                if(j-k<=0) continue; //n은 양수
                dp[j][i] += dp[j-k][i-1];
                dp[j][i] %= MOD;
            }
        }
    }

    while(T--)
    {
        cin >> n >> m;
        ll result = 0;
        for(int i=1; i<=m; i++) result += dp[n][i];
        cout << result%MOD << "\n";
    }

    return 0;
}

 

백준 15992번 1, 2, 3 더하기 7번 문제와 매우 유사한 문제이다.

알고리즘 방식은 똑같고, 해당 문제의 경우 m번 사용한 경우를 구하는 것이기 때문에 dp[n][m]을 출력했지만,

이번 문제는 m번 이하만큼 사용한 경우를 모두 체크해야 하므로 dp[n][1~m]까지 모두 더한 값을 출력하게 된다.

이 더하는 과정에서 누적합을 저장하는 result의 범위가 int 값을 초과할 가능성이 존재하기 때문에 long long으로 선언한다.

 

참고링크 : https://blob-thinking.tistory.com/429

[백준 15992번] 1, 2, 3 더하기 7 (C++)