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

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

15993번: 1, 2, 3 더하기 8

using namespace std;
 
int t, n, maxN;
vector<int> answers;
unsigned int dp[100001][2] = { 0 };
const int MOD = 1000000009;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    while (t--)
    {
        cin >> n;
 
        maxN = max(maxN, n);
        answers.push_back(n);
    }
 
    dp[1][1] = 1;
    dp[2][0] = 1;
    dp[2][1] = 1;
    dp[3][0] = 2;
    dp[3][1] = 2; 
    dp[4][0] = 4;
    dp[4][1] = 3;
 
    for (int i = 5; i <= maxN; ++i)
    {
        for (int j = 0; j < 2; ++j)
        {
            int isOdd = (j + 1) % 2;
 
            dp[i][j] += (dp[i - 1][isOdd]) % MOD;
            dp[i][j] += (dp[i - 2][isOdd]) % MOD;
            dp[i][j] += (dp[i - 3][isOdd]) % MOD;
        }
    }
 
    for (int i = 0; i < answers.size(); ++i)
    {
        printf("%d %d\n", dp[answers[i]][1] % MOD, dp[answers[i]][0] % MOD);
    }
}
 
 
 
 

 

이번엔 각 수를 구성하는 짝수, 홀수의 경우의개수를 구하는 문제이다.

이전문제들을 풀었던것들과 비슷하게 생각해서 풀 수 있었다.

 

예를들어 숫자5의 짝수,홀수 경우의개수를 구하는 경우를 생각해보자.

숫자 1,2,3을만을 붙일 수 있으니, 숫자5의 짝수의 개수 중 한묶음은 숫자4를 이루는 '홀수'의 개수가 될 것이다.

숫자 4에다가 숫자 1을붙이면 숫자 5가 됨이 동시에, 짝수가 되기 때문이다. (홀수의 개수에 1개를 붙였으니 짝수)

마찬가지 원리로 숫자3을 이루는 홀수의 개수에다가 숫자2를 붙이면 숫자 5가 됨이 동시에 짝수가된다.

마지막으로 숫자2를 이루는 홀수의 개수에다가 숫자3을 붙이면 숫자 5가 됨이 동시에 짝수가 된다.