[백준 15993번] 1, 2, 3 더하기 8 (C++)

문제링크 : https://www.acmicpc.net/problem/15993

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, n;
ll dp[100001][2]; //짝 0, 홀 1
const int MOD = 1000000009;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> T;
    dp[1][1] = 1; //1
    dp[2][0] = dp[2][1] = 1; //1,1 / 2
    dp[3][0] = dp[3][1] = 2; //1,2 2,1 / 1,1,1 3

    for(int i=4; i<100001; i++) //숫자
    {
        dp[i][0] = (dp[i-1][1] + dp[i-2][1] + dp[i-3][1]) % MOD; //짝수
        dp[i][1] = (dp[i-1][0] + dp[i-2][0] + dp[i-3][0]) % MOD; //홀수
    }

    while(T--)
    {
        cin >> n;
        cout << dp[n][1] << " " << dp[n][0] << "\n";
    }

    return 0;
}

 

dp식을 짝수인 경우와 홀수인 경우를 고려하여 2차원 배열로 선언해준다.

순서는 숫자 n, 짝 홀 여부이다.

 

우리가 활용하는 숫자는 1~3까지이므로 이에 맞게 1~3까지 초기값을 부여해준다.

숫자가 작기에 직접 계산하여 쉽게 구할 수 있다.

 

이후 i=4부터 10만까지 미리 계산을 해준다.

해당 i기준 짝수인 경우는 i-1, i-2, i-3을 각각 홀수개로 표현한 수 + 각 1, 2, 3으로 표현한 가짓수이다.

홀수 인경우는 반대로 i-1, i-2, i-3을 각각 짝수개로 표현한 수 + 각 1, 2, 3으로 표현한 가짓수이다.

예제를 통해 살펴보면 다음과 같다.

n=4

<짝수>
1+1+1+1
2+2
1+3
3+1

dp[4-1][1] = 3 홀수개로 표현 + 1로 표현 -> 1 (3, 1)
dp[4-2][1] = 2 홀수개로 표현 + 2로 표현 -> 1 (2, 2)
dp[4-3][1] = 1 홀수개로 표현 + 3으로 표현 -> 2 (1, 1 + 1 + 1 / 1, 3)

<홀수>
1+1+2
1+2+1
2+1+1

dp[4-1][0] = 3 짝수개로 표현 + 1로 표현 -> 2 (1 + 2, 1 / 2 + 1, 1)
dp[4-2][0] = 2 짝수개로 표현 + 2로 표현 -> 1 (1 + 1, 2)
dp[4-3][0] = 1 짝수개로 표현 + 3으로 표현 -> 0

 

이후 입력받은 n에 대해 홀수의 경우와 짝수의 경우를 순서대로 출력해주면 된다.