백준 재활치료 (2) 31836번 : 피보나치 기념품

바로 이어가는 2번째 문제
피보나치라고 하는거 보니 당연히 dp쪽 문제 아닐까? 아직 읽기 전이다

애드 혹 문제였다, 이러한 문제들은 대부분 패턴이 존재한다

그래서 한 9번째까지 스스로 돌리면서 패턴을 찾아봤다

글씨가 이상해서 아쉽지만 아무튼
2라는 예외를 제외하고 3의 배수를 중심으로
N을 오른쪽 / N-1, N-2를 왼쪽으로 보내며
3의 배수를 기준으로
나머지가 0이면 딱 맞고
나머지가 1이면 맨 앞 부분만 빼고
나머지가 2이면 1,2번을 각각 왼, 오른쪽에 분배하고 나머지를 분배하면
정확히 조건에 맞는다는 것을 알 수 있었다

그래서 정의한 식이

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;

    int a = 0;
    int c = 0;
    vector<int> b(0);
    vector<int> d(0);

    if (N == 2) {
        cout << 1 << '\n';
        cout << 1 << '\n';
        cout << 1 << '\n';
        cout << 2 << '\n';
        return 0;
    }

    int r = N % 3;

    if (r == 0) {
        for (int i = N; i > 0; i -= 3) {
            d.push_back(i);
            b.push_back(i - 1);
            b.push_back(i - 2);
        }
    }
  
    else if (r == 1) {

        for (int i = N; i > 4; i -= 3) {
            d.push_back(i);
            b.push_back(i - 1);
            b.push_back(i - 2);
        }      
        d.push_back(4);
        b.push_back(1);
        b.push_back(3);
    }

    
    else if (r == 2) {
       
        b.push_back(1);
        d.push_back(2);

        for (int i = N; i > 2; i -= 3) { 
            d.push_back(i);
            b.push_back(i - 1);
            b.push_back(i - 2);
        }
    }

    sort(b.begin(), b.end());
    sort(d.begin(), d.end());

    a = (int)b.size();
    c = (int)d.size();

    cout << a << '\n';
    for (int i = 0; i < a; i++) {
        cout << b[i] << " ";
    }
    cout << '\n';

    cout << c << '\n';
    for (int i = 0; i < c; i++) {
        cout << d[i] << " ";
    }
    cout << '\n';

    return 0;
}

이런 식으로 조건에 맞춰 push_back 하는 방향으로 계산을 했다
간단히 설명하자면
2를 예외로 두어 답을 출력하고
3부터 N부터 -2씩 내려가며 분배를 하며 방금 구한 3의 배수를 기준으로 각 항을 맞춰주었다

그 후 숫자를 정렬해 맞춰주며 출력하며 마무리했다

여기서 한번 틀린 예외는 4의 예외였는데
생각해보니 4에서 들어가는 1은 1번의 1, 2번의 1 둘 다 가능한 부분이였어서 문제 자체의 규칙대로 넣어두기로 했다
문제 자체는 1을 넣는 것을 기준으로 하는 것 같아서 4 이상부터 정상적으로 쌓이고 4는 그냥 직접 넣어버리며 문제를 해결했다

패턴 찾는거 자체는 막 어렵진 않았는데 이를 식화시키는 부분에서 조금 애를 먹었던 것 같다