문제
세림이랑 성주는 왜 대체 피보나치 수열을 좋아하는 걸까…? 아무튼 두 사람이 받게 될 기념품에 적힌 피보나치 수의 합이 같아야 하면서 최대한 많은 개수의 기념품을 나눠줄 수 있도록 해야한다.
입출력을 보자.
예제 1의 경우 2개의 기념품이 있다.
이 때, 세림이는 1이 적혀있는 기념품 한개를 받았고, 성주는 2가 적혀있는 기념품 한 개를 받았다.
여기서 1과 2 모두 피보나치 수로 1이기 때문에 두 사람이 받은 기념품들의 합은 1로 같다.
예제2의 경우 4개의 기념품을 받았다. 세림이는 1, 3 두 개의 기념품을 받았고, 성주는 4로 된 기념품 하나를 받았다. 세림이의 기념품들의 피보나치 수 합은 F1+F3 = 1+2 = 3 성주의 기념품들의 피보나치 수 합은 F4 = 3 이므로 두 사람이 받은 기념품의 피보나치 수 합은 같다.
이 문제는 어떻게 풀어야 할까? N이 주어지면 거기에서 공통의 합의 나오도록 해야 하는데, 이는 한 사람의 기념품을 받은 수를 가지고 계속 쪼갤 수 있다. 예제 2처럼 N이 4라고 한다면 F4부터 시작해서 계속해서 피보나치 수로 쪼갤 수 있도록 하는 것이다. 예제 2의 경우도 4로 시작해서 F4 = F2 + F3이므로 한도를 넘지 않는 선에서 2개의 기념품을 가지도록 한 것이다. 또한 여기서 최대의 값을 가져야 하므로 기존에 나온 값들 중에서 가장 큰 값을 고르는 것이기 때문에 분할정복 혹은 dp로 풀어야 할 것 같다. 흠 일단 피보나치로 나올 수 있는 수들에 대해서 미리 메모이제이션 한 다음에, 여기에서 가장 크게 나눠가질 수 있는 경우를 찾아보면 될 것 같다. 샀던 N개의 기념품은 모두 N보다 작은 x의 수가 적혀있는 피보나치 수이다. 가장 큰 수부터 시작해서 계속 피보나치를 나눠가면서 개수를 더하면?