백준 15992 1,2,3 더하기 7

백준 15992 1,2,3 더하기 7

---

이번에는 1,2,3 더하기 문제를 풀었다. 이 유형이 7문제나 있다는거에 놀랐다! 나 한개밖에 안해본거 같은데.. ㅎ

전에 풀었던 문제와의 차이점은 m 개의 숫자만을 사용하여야 한다는 점이 었다.

그래서 dp 배열을 만들어 점화식

dp[i][n] = dp[i-1][n-1] + dp[i-2][n-1] + dp[i-3][n-1]

을 세웠다. 이는 i 란 수를 만드는데에는, i-1 을 n-1 개의 (1,2,3)을 사용해 만든 경우와, i-2 를 n-1 개 사용해 만든 경우, i-3을 n-1개의 숫자를 사용해 만든 경우. 를 다 합치면 된다는 의미이다.

다 풀었는데 시간 초과가 나서 보니, 문제마다 dp를 할게 아니라, 1000x1000 사이즈에 대해 전부다 구하놓고 입력을 받으면 dp[n][m] 을 출력하여아만 시간초과가 안나는 문제였다.

#include <iostream>
#include <vector>

using namespace std;

long dp[1002][1002];

int main()
{

    int tc;

    cin>>tc;

    dp[1][1] = 1;
    dp[1][2] = 0;
    dp[1][3] = 0;

    dp[2][1] = 1;
    dp[2][2] = 1;

    dp[3][1] = 1;
    dp[3][2] = 2;
    dp[3][3] = 1;

    dp[4][1] = 0;
    dp[4][2] = 3;//2 2, 3,1 1,3
    dp[4][3] = 3;  //1,1,2  1,2,1 2,1,1 
    dp[4][4] = 1;


    for (int i = 3; i <=1000; i++)
    {
        dp[i][2] = dp[i-1][1] + dp[i-2][1] + dp[i-3][1];

        for (int j = 3; j<=1000; j++)
        {
            dp[i][j] = (dp[i-1][j-1] + dp[i-2][j-1]+ dp[i-3][j-1]) % 1000000009;
        }  
    }

    for (int i = 0; i < tc; i++)
    {
        int n, m;
        cin>>n>>m;
        //dp를, n 을 만드는데는, 
        // n-1 를 만드는데 m-1개의 수를 사용한 경우
        // n-2 를 만드는데 m-개의 수를 사용
        // n-3 을 만드는데 m-1개의 수를 사용한경우를
        // 즉, dp[n][j] = dp[n-1][j-1] + dp[n-2][j-1] + dp[n-3][j-1];

        cout<<dp[n][m]<<"\n";
    }

    return 0;
}

암튼 오늘도 2개의 dp 문제를 푸는데 성공했다! 꾸준히 하면 방법이 보일겨