[Algorithm]Baekjoon 15993번 :: 1,2,3 더하기 9

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

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

 
 
using namespace std;
 
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 });
    }
 
    for (int i = 1; i <= maxM; ++i)
    {
        dp[1][i] = 1;
    }
 
    dp[2][1] = 1;
    for (int i = 2; i <= maxM; ++i)
    {
        dp[2][i] = 2;
    }
 
    dp[3][1] = 1;
    dp[3][2] = 3;
    for (int i = 3; i <= maxM; ++i)
    {
        dp[3][i] = 4;
    }
 
    for (int i = 4; i <= maxN; ++i)  
    {
        for (int j = 2; j <= i; ++j) 
        {
            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;
            }
        }
 
        for (int j = i + 1; j <= maxM; ++j)
        {
            dp[i][j] = dp[i][i];
        }
    }
 
    for (int i = 0; i < answers.size(); ++i)
    {
        printf("%d\n", dp[answers[i].first][answers[i].second] % MOD);
    }
}
 
 
 

 

1,2,3더하기 시리즈 마지막 문제이다. 이것도 생각보다 빠르겐 아니지만, 자력으로 풀 수 있었다.

m개 이하의 경우의개수를 구하는 것이기 때문에 한번 아래와 같이 dp테이블을 잡아봤다.

 

dp[5][3] 이라면, 숫자 5를 구성하는 3개이하의 경우의개수를 의미한다.

그렇기 때문에 [5][5] 이후의 값들, 즉 [5][6]이나 [5][6] .......[5][1000]까지의 값들은 [5][5]와 전부 동일하다.

[5][2]가 [5][1]의 값을 포함하고있고, [5][3]은 [5][2]의 값들을 포함한다. m개이하의 값들이니까.

 

이런 가정하에 코드를 작성했다. 이전문제와 비슷하게, [5][3], 즉 숫자 5를 3개이하의 숫자로 구성하려면 일단 숫자 1을 붙이려한다면 숫자 4에다가 붙여야한다. 그리고 3개이하를 맞춰야하니 2개이하인거에 붙여야 한다.

즉, dp[5][3] += dp[4][2] 가 된다. 나머지 숫자도 마찬가지로

dp[5][3] += dp[3][2] // 숫자 2를 붙이는 경우

dp[5][3] += dp[2][2] //숫자 3을 붙이는 경우 

 

이렇게 생각하고 작성하고 제출했는데 특정값인덱스 이후로 값이 부족하길래 알아봤더니 미리 값을 넣언왔던 1,2,3값들에 대해서도 maxM까지 테이블에 값을 채워넣어야 했었다.

그래서 생각보다 코드가 더 길어지긴 했다.

그래도 시간은 4ms로 양호하게 나온다.

 

다른사람풀이를 보면은 dp테이블을 이전문제처럼 그냥 dp[i][j]는 숫자 i를 j개의 개수로 구성된 경우의 개수..로 정의했다.

그리고 마지막에 출력했을 때 dp[i][1]부터 dp[i][m]까지 전부 합산 후 출력한다.

보고나니, 그렇게 해도 당연히 될 것같다는 생각을 했다. 코드도 더 짧기도하고, 수행속도는 같고.. 

하지만 수행속도도 같기도하고, 해당테이블 정의하는것도 이전문제들에서 많이 해봐서, 다음에 비슷한 문제를 봤을 때 풀 수 있을 것 같아서 굳이 코드를 수정하지는 않았다.

 

그리고 mod연산(%)은 시간이 걸리니, 거를 수 있으면 거르는게 좋다.

위의 내 코드에서 49,54,59라인을 보면 0값이 아닌경우에만 mod연산해서 dp[i][j]에 합연산을 하는데, 해당 if문이 없어도 당연히 통과한다. 어차피 0이여도 mod연산하면 0이라서 상관없다.

하지만 해당 if문 없이 제출하면 원래 4ms나오던게 8ms가 나온다. 안했던 mod연산을 전부 수행하기 때문에 그런 것 같다