[Algorithm]Baekjoon 15990번 :: 1,2,3 더하기 5

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

15990번: 1, 2, 3 더하기 5

 
 
int t, n;
int dp[100001][4] = { 0 };
const int mod = 1000000009;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> t;
 
    vector<int> inputs;
    int maxNum = 0;
 
    while (t--)
    {
        cin >> n;
        inputs.push_back(n);
        maxNum = max(maxNum, n);
    }
 
    dp[1][1] = 1;
    dp[2][2] = 1;
    dp[3][1] = 1;
    dp[3][2] = 1;
    dp[3][3] = 1;
    
    for (int i = 4; i <= maxNum; ++i)
    {
        dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % mod;
        dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % mod;
        dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % mod;
    }
 
    for (int i = 0; i < inputs.size(); ++i)
    {
        long long result = (long long)dp[inputs[i]][1] + dp[inputs[i]][2]  + dp[inputs[i]][3];
        printf("%d\n", result % mod);
    }
}

 

특정 수를 만들때 특정 숫자만 사용해야하는데, 연속되어선 안되는 문제이다.

이 문제의 하위호환인 9095번문제인 1,2,3 더하기 문제에서 좀 더 조건이 달린 문제다.

 

숫자가 연속되면 안된다는 조건때문에, 기존의 1,2,3 더하기 문제풀이와 아예 달라진다.

연속되지 않으려면 아래와 같아야한다.

 

n번째에서 1로 끝나려면, n-1번째에서 2나 3으로 끝나야 한다.

n번째에서 2로 끝나려면, n-2번째에서 1이나 3으로 끝나야 한다.

n번째에서 3으로 끝나려면,  n-3번째에서 1이나 2로 끝나야한다.

 

이 조건들을 살짝 다르게 해석해보겠다.

 

n번째 차례때 숫자 1을 추가하고싶으면, n-1번째에서 2나 3으로 끝나야한다.

1을 추가하기 때문에 'n-1'번째에서 2나 3으로 끝나야 하는것이다.

나머지것들도 마찬가지. 숫자 2를 추가하고싶으면, n-2번째에서 추가해야하고 숫자 3을 추가하고 싶으면 n-3번째에서 추가해야한다. 

추가할 때 숫자가 연속되면 안되니, 2를 추가하고싶으면 n-2번째에서 1과 3으로 끝나는 경우의수가 필요하고 3을 추가하고싶으면 n-3번째에서 1과 2로 끝나는 경우의 수가 필요한 것이다.

 

그리고 테스트케이스가 여러개가 주어지기 때문에 dp테이블업데이트를 굳이 테스트케이스마다 해줄필요는 없다.

테스트케이스중 가장 큰값을 구해서 해당값으로 한번만 수행하면 된다.

아니면 n값이 최대 10만이니 10만으로 한번 해버리던가..

 

그리고 1000000009로 나눈 나머지를 출력해야한다는걸 명심하자.

dp테이블자체는 int로해도 상관없다. 어차피 업데이트할 때 n-1의 테이블값 두개만 더하기 때문에, 최대값인 1000000008 * 2 해도 int 범위로 충분히 커버된다. 그냥 4바이트짜리 int면 21억 4천 7백만..... 까지 커버된다.

 

하지만 최종적으로 답을 출력해야할 때는 값 3개를 더해야하기 때문에(dp[n][1] + dp[n][2] + dp[n][3]) 그냥 세개 더한다음 mod 하면 안되고, long long에 임시로 더한값을 넣어놓은 후, mod해서 출력하면 된다.

40번째라인처럼 long long 변수에 값을 대입하는 식이더라도, int로 되어있는 dp값들 3개중에서 한개에는 반드시 (long long)으로 묵시적변환을 해놔야 long long크기의 임시메모리에 3개의 dp값을 합친값이 저장된 후, result에 전달된다.

안그러면 int크기의 임시메모리에 저장되기때문에 값이 잘릴것이다.