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

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

 

#include <iostream>
using namespace std;

int mod = 1000000009;
long long s[100001] = {0};

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

    s[1] = 1;
    s[2] = 2;
    s[3] = 4;
    for (int i = 4; i < 100001; i++) {
        s[i] = (s[i - 1] + s[i - 2] + s[i - 3]) % mod;
    }

    int t;
    cin >> t;

    for (int tn = 0; tn < t; tn++) {
        int n;
        cin >> n;

        long long ans = 0;
        if (n == 1 || n == 2) {
            ans = n;
        } else if (n == 3) {
            ans = 2;
        } else if (n % 2 == 0) {
            ans = (s[n / 2] + s[(n - 2) / 2]) % mod;
        } else {
            ans = (s[(n - 1) / 2] + s[(n - 3) / 2]) % mod;
        }
        cout << ans << '\n';
    }
}

전에 풀었던 1, 2, 3 더하기 문제를 활용해서 풀었다. (정답)

1, 2, 3 더하기 문제 (백준 9095번) : https://www.acmicpc.net/problem/9095

내 풀이 : https://jungh150c.tistory.com/96