15993 1, 2, 3 더하기 8

 

 

빡쳐~~~~~~~~~

 

처음부터 설계를 잘 해야 한다는 걸 느낀 문제

 

이걸 어떻게 생각했냐면 위의 사진보면 같은 색깔로 묶인거

 

저걸 사용해서 메모이제이션을 하려고 했다 이게 규칙인줄 알았음

 

그래서 나온 코드가 아래임 더럽고 짜면서도 스트레스 받음ㅠ 

 

나중에 풀면서 어...? 그냥 3 더하려면 i-3에서 더하고, 2 더하려면 i-2에서 더하고, 1 더하려면 i-1에서 더하면 되잖아...? 싶었음

 

아 그리고 생각난 거 더

 

저거 힘들게 pair로 하지말고 짝수 / 홀수 저장하는 배열 두 개를 두고 풀면 좋겠다

 

 

#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>;

ii64 v[100005][3];

int main() 
{
    //xx = 짝수, yy = 홀수

    v[1][0].yy = 1;

    v[2][0].xx = 1;
    v[2][1].yy = 1;

    v[3][0].yy = 1;
    v[3][1].xx = 2;
    v[3][2].yy = 1;

    for (int i = 4; i <= 100000; i++)
    {
        if (i % 2 == 0)
        {
            v[i][0].xx = 1;

            v[i][1].yy += v[i - 2][0].xx % MOD; //
            v[i][1].yy += v[i - 2][1].xx % MOD; //
            v[i][1].yy += v[i - 1][1].xx % MOD; //

            v[i][1].xx += v[i - 1][1].yy % MOD; //
            v[i][1].xx += v[i - 2][1].yy % MOD; //
            
            v[i][2].yy += v[i - 3][2].xx % MOD; //
            v[i][2].xx += v[i - 3][2].yy % MOD;

            v[i][2].yy += v[i - 3][1].xx % MOD; //
            v[i][2].xx += v[i - 3][1].yy % MOD;

            v[i][2].yy += v[i - 3][0].xx % MOD;
            v[i][2].xx += v[i - 3][0].yy % MOD;

            continue;
        }

        v[i][0].yy = 1;

        v[i][1].xx += v[i - 2][0].yy % MOD;

        v[i][1].xx += v[i - 2][0].yy % MOD;
        v[i][1].yy += v[i - 2][0].xx % MOD;

        v[i][1].xx += v[i - 2][1].yy % MOD;
        v[i][1].yy += v[i - 2][1].xx % MOD;

        v[i][1].xx += v[i - 1][1].yy % MOD;
        v[i][1].yy += v[i - 1][1].xx % MOD;

        v[i][2].xx += v[i - 3][0].yy % MOD;
        v[i][2].yy += v[i - 3][0].xx % MOD;

        v[i][2].xx += v[i - 3][1].yy % MOD;
        v[i][2].yy += v[i - 3][1].xx % MOD;

        v[i][2].xx += v[i - 3][2].yy % MOD;
        v[i][2].yy += v[i - 3][2].xx % MOD;

        if (i == 7)
        {
            printf("%lld %lld\n", v[i][0].xx, v[i][0].yy);
            printf("%lld %lld\n", v[i][1].xx, v[i][1].yy);
            printf("%lld %lld\n\n", v[i][2].xx, v[i][2].yy);
        }

        
    }

    int t;
    cin >> t;

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

        i64 a = v[n][0].xx % MOD + v[n][1].xx % MOD + v[n][2].xx % MOD;
        i64 b = v[n][0].yy % MOD + v[n][1].yy % MOD + v[n][2].yy % MOD;

        printf("%lld %lld\n", b, a);
    }



    return 0;
}

 

이렇게 생각하고 구현하려 했으나 디코에서 풀이 보고 dp배열 하나만 써도 되겠다 싶었음

 

위 코드처럼 v[i][3]으로 만들지 말고..

 

 

---

#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 v[100005][2];

int main() 
{
    v[1][1] = 1;

    v[2][0] = 1;
    v[2][1] = 1;

    v[3][0] = 2;
    v[3][1] = 2;

    for (int i = 4; i <= 100000; i++)
    {
        v[i][0] = v[i - 1][1] % MOD + v[i - 2][1] % MOD + v[i - 3][1] % MOD;
        v[i][1] = v[i - 1][0] % MOD + v[i - 2][0] % MOD + v[i - 3][0] % MOD;
    }

    int t;
    cin >> t;

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

        printf("%lld %lld\n", v[n][1] % MOD, v[n][0] % MOD);
    }

    return 0;
}

\ㅠㅠㅠㅠ 간단하다 정말

 

처음에 printf 할 때 MOD로 안 나눠줘서 한 번 틀렸음.

 

위에 반복문 돌릴 때 MOD 해줘서 괜찮은 줄 알았지..