[중등부] 2025 KOI 1차대회 대비 파이널 모의고사

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

• F_1=1 

• F_2=1 

• F_n=F_{n-1}+F_{n-2} (단, n\ge 3)

농부 존은 우(牛)시장에서 인식표에 1부터 N까지 번호가 적혀 있는 N마리의 소들을 구매했다.

이 소들은 특이하게도 번호가 x(1\le x\le N)번인 소는 F_x개의 얼룩이 있다.

농부 존은 피보나치 수열을 좋아하는 베시와 엘시가 각각 우두머리로 있는 두 목장에 이번에 새로 구매한 소들을 분배하려고 한다. 하지만 한 목장에 너무 많은 소들이 들어가면 소가 많이 들어온 목장은 너무 붐빌 수 있기 때문에, 두 목장에 배치되는 소들의 얼룩 개수의 합이 같아지도록 소들을 분배하려고 한다. 조건이 맞지 않는다면 일부 소는 다시 환불을 해야 할 수도 있다. 그래도 최대한 많은 수의 소들을 목장에 넣고자 한다.

환불하는 소의 수를 최소화하면서, 두 목장에 새롭게 배치되는 소들의 얼룩 개수의 합이 같도록 소들을 배치하는 방법을 구해보자. 두 목장에 한 마리 이상의 소가 배치되는 방법은 항상 존재한다.