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

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

15992번: 1, 2, 3 더하기 7

#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;
        cout << dp[n][m] << "\n";
    }

    return 0;
}

 

목표 값과 현재 숫자 갯수를 참고하여 2차원 dp 배열을 선언한다. (dp[n][m])

먼저 숫자 1, 2, 3에 대해 숫자 갯수가 1개인 경우는 올 수 있는 경우가 1가지 뿐이므로 각 케이스를 1로 초기화 해준다.

 

이후 3중 반복문을 돌리게 된다.

첫 번째 인덱스는 i=2부터 1000까지 갯수를 의미하고,

두 번째 인덱스는 목표 값을 의미하고,

세 번쨰 인덱스는 가능한 숫자 1, 2, 3을 의미한다.

우선 n은 양수이기에 j-k의 값이 0보다 작거나 같다면 스킵한다.

 

j-k가 현재 목표 값이고, k는 1~3까지 이동하기에 1을 이용한 값, 2를 이용한 값, 3을 이용한 값을 체크가 가능하다.

현재 값에 대해 1을 이용한 케이스는 dp[j-1][i-1],

현재 값에 대해 2를 이용한 케이스는 dp[j-2][i-1],

현재 값에 대해 3을 이용한 케이스는 dp[j-3][i-1]이 된다.

 

이후는 앞에서 설정했던 값들을 다시 이용하여 dp 식을 갱신하게 된다.