15988 1, 2, 3 더하기 3

 

ㅋㅋㅋㅋㅋㅋ

문제 정신놓고 읽다가 1개 이상을 2개 이상으로 생각했다

 

열심히 풀었음..

아! 4개 부터는 무조건 2개 이상을 만족하니깐 1개 이상으로 구현한 다음에 1, 2, 3 부분만 2개 이상으로 반영해야지!

 

틀리고 나서 깨달음

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MOD 1000000009

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

i64 cache[1000005];

int     main()
{
    cache[1] = 1;
    cache[2] = 2;
    cache[3] = 4;

    for (int i = 4; i <= 1000001; i++)
        cache[i] = cache[i - 1] % MOD + cache[i - 2] % MOD + cache[i - 3] % MOD;

    int t;
    scanf("%d", &t);

    for (int i = 0; i < t; i++)
    {
        int n;
        scanf("%d", &n);

        printf("%lld\n", cache[n] % MOD);
    }

    return 0;
}

 

이 문제 처음 풀 때 몰라서 별 해괴한 방식으로 풀었는데 몇 번 푸니깐 어떻게 풀지 보이는 것 같다.

 

다른 문제도 이 문제처럼 틀리면서 배우는 게 있겠지