[Algorithm]Baekjoon 15992번 :: 1,2,3 더하기 7

https://www.acmicpc.net/problem/15992

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

 
 
int t, n, m, maxN, maxM;
vector<pair<int, int>> answers;
unsigned int dp[1001][1001] = { 0 };
const int MOD = 1000000009;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    while (t--)
    {
        cin >> n >> m;
 
        maxN = max(maxN, n);
        maxM = max(maxM, m);
        answers.push_back({ n,m });
    }
 
    dp[1][1] = 1;
    dp[2][1] = 1;
    dp[2][2] = 1;
    dp[3][1] = 1;
    dp[3][2] = 2;
    dp[3][3] = 1;
 
    for (int i = 4; i <= maxN; ++i)
    {
        for (int j = 2; j <= maxM; ++j) // 어차피 i값이 4부터는 j가 1인것들은 전부 0이라서
        {
            if (dp[i - 1][j - 1] != 0)
            {
                dp[i][j] += (dp[i - 1][j - 1]) % MOD;
            }
 
            if (dp[i - 2][j - 1] != 0)
            {
                dp[i][j] += (dp[i - 2][j - 1]) % MOD;
            }
 
            if (dp[i - 3][j - 1] != 0)
            {
                dp[i][j] += (dp[i - 3][j - 1]) % MOD;
            }
        }
 
        dp[i][i] = 1; // 1로만 이루어져 있다.
    }
 
    for (int i = 0; i < answers.size(); ++i)
    {
        printf("%d\n", dp[answers[i].first][answers[i].second] % MOD);
    }
}
 
 
 

 

1,2,3더하기라는 문제형태에 익숙해져서 그런가, 이번에는 순수자력으로 풀 수 있었다.

각 숫자를 m자리수로 구성되어있는 경우의개수를 구해야하는데, 사용할 수 있는 숫자는 1,2,3밖에 없으니 숫자 1을붙이려면 i-1에다가 붙여야하며, m자리수를 맞춰야하기 때문에 j-1에다가 붙여야 한다.

 

즉, dp[5][3] == 숫자 5를 만들 때, 3개의 숫자로 구성하려는 경우의 개수

라고 dp테이블을 정의했을 때, 숫자 1을 붙이려면 4에다가 붙여야하고 3개의 숫자로 구성해야하니, 숫자 2개로 4를 구성하는 경우의개수를 알아야한다.

그렇기 때문에 아래와 같은 점화식이 성립된다.

dp[i][j] += dp[i-1][j-1];

 

숫자는 1뿐만 아니라 2,3도 있으니 최종적으론 다음과 같다.

 

dp[i][j] += dp[i-1][j-1];

dp[i][j] += dp[i-2][j-1];

dp[i][j] += dp[i-3][j-1];

 

여기서 무조건 더하는게 아니라 dp[i-1][j-1]값이 0일 경우에는 더하면 안된다. 하나라도 존재해야 거기에 숫자를 붙이는건데, 아예 존재하지않는것에 숫자를 붙일 순 없으니까.

 

그리고 dp[i][i]값은 무조건 1이기 때문에 m값에 관한 반복문 진행 후, 마지막에 dp[i][i]는 1로 덮어 씌워줘야 한다.

각 숫자의 해당숫자개수만큼의 숫자로 이루어진 경우의개수는 단 한개밖에 존재하지않는다.

바로 1로 구성되어진것들이다.

 

그리고 mod값이 1000000009이기 때문에, unsigned int로 해도 오버플로우는 일어나지 않으니 사용해도 된다.