boj 15993 1, 2, 3 더하기 8

 

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

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

1, 2, 3 더하기 8번째 문제입니다.

이 문제는 7번째 문제와 비슷한 유형이라고 볼 수 있습니다.

7번째 문제에서는 M개의 수를 사용하여 N을 만드는 방법인데 이를 홀수, 짝수로 나누면 되는 문제입니다.

 

dp[N][0] → N을 만드는 방법 중 홀수개를 사용하는 경우

dp[N][1] → N을 만드는 방법 중 짝수개를 사용하는 경우

 

7번째 문제에서 dp[N]는 dp[N - 1]에서 +1, dp[N - 2]에서 +2, dp[N - 3]에서 +3을 한 것이라고 했었습니다.

즉, 갯수가 1개가 늘어난다는 말은 홀수는 짝수가 되고, 짝수는 홀수가 된다는 말입니다.

 

따라서 홀수의 갯수는 N - 1, N - 2, N - 3번째의 수를 짝수개를 사용하여 나타내는 방법의 수를 더한 값이고,

짝수의 갯수는 N - 1, N - 2, N - 3번째의 수를 홀수개를 사용하여 나타내는 방법의 수를 더한 값이 되겠습니다.

 

 

#include <iostream>
#define MOD 1000000009
using namespace std;
 
int dp[100001][2];
 
void init() {
    dp[1][0] = 1;
    dp[2][0] = 1;
    dp[2][1] = 1;
    dp[3][0] = 2;
    dp[3][1] = 2;
    for (int i = 4; i <= 100000; i++) {
        dp[i][0] = ((dp[i - 1][1] + dp[i - 2][1]) % MOD + dp[i - 3][1]) % MOD;
        dp[i][1] = ((dp[i - 1][0] + dp[i - 2][0]) % MOD + dp[i - 3][0]) % MOD;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    init();
    int tc, N;
    cin >> tc;
    while (tc--) {
        cin >> N;
        cout << dp[N][0] << ' ' << dp[N][1] << '\n';
    }
 
    return 0;
}