백준 31836 (C++) 피보나치 기념품

최초 업로드: 2025-04-17 21:54:39

최근 수정 시간: 2025-07-25 09:42:06

게시자: rlatjwls3333

카테고리: 백준

# [Silver I] 피보나치 기념품

[문제 링크](https://www.acmicpc.net/problem/31836)

## 문제 설명

피보나치 수열은 다음과 같이 정의되는 수열이다.

정휘는 이집트 룩소르의 한 시장에서 피보나치 수가 적혀 있는 $N$개의 기념품을 구매했다. $x(1le xle N)$번 기념품에는 $F_x$가 적혀 있다.

정휘는 피보나치 수열을 좋아하는 세림이와 성주에게 기념품을 선물하려고 한다. 하지만 한 명에게 너무 많은 기념품을 주면 기념품을 적게 받은 사람이 슬퍼할 수 있기 때문에, 두 명이 받게 될 기념품에 적힌 피보나치 수의 합이 같아지도록 선물을 분배하려고 한다. 구매한 기념품의 개수 $N$에 따라 $N$개의 기념품을 전부 나눠주지 못할 수 있는데, 이때는 최대한 많은 개수의 기념품을 나눠주려고 한다.

나눠주는 기념품의 개수를 최대화하면서, 두 명이 받는 기념품에 적힌 수의 합이 같도록 기념품을 나눠주는 방법을 구해보자. 두 사람에게 1개 이상의 기념품을 나눠주는 방법은 항상 존재한다.

## 입력

첫째 줄에 정휘가 구매한 기념품의 개수 $N$이 주어진다.

## 출력

첫째 줄에 세림이가 받을 기념품의 개수 $X$를 출력한다.

둘째 줄에 세림이가 받을 기념품들의 번호 $A_1,A_2,cdots ,A_X$를 공백으로 구분해서 출력한다.

셋째 줄에 성주가 받을 기념품의 개수 $Y$를 출력한다.

넷째 줄에 성주가 받을 기념품들의 번호 $B_1,B_2,cdots ,B_Y$를 공백으로 구분해서 출력한다.

가능한 분배 방법이 여러 가지면 그중 아무거나 하나만 출력하라.

## 풀이
#### Fn = Fn-1 + Fn-2이기에 항상 연속한 3개의 수는 두 사람에게 똑같이 나누어 줄 수 있다. 따라서 큰 수부터 3개씩 나누어 가지면 된다. 다만 마지막 1 1 인 경우 예외적으로 2개로 나눌 수 있다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;

vector<int> X, Y;
 while(n>1) {
 if(n-3>=0) {
 X.push_back(n);
 Y.push_back(n-1);
 Y.push_back(n-2);
 n-=3;
 }
 if(n==2) {
 X.push_back(2);
 Y.push_back(1);
 n-=2;
 }
 }

cout << X.size() << '\n';
 for(int e:X) cout << e << ' ';
 cout << '\n' << Y.size() << '\n';
 for(int e:Y) cout << e << ' ';
}
```