[BOJ 23603] Fibonaccis’ vouchers

문제: https://www.acmicpc.net/problem/23603

 

풀이:

Zeckendorf's Theorem을 살펴봅시다.

 

Zeckendorf's Theorem: 모든 양의 정수는 인접하지 않은 서로 다른 피보나치 수의 합으로 유일하게 표현할 수 있다. (Zeckendorf Representation)

 

예를 들면, $64 = 55 + 8 + 1$ 처럼 인접하지 않은 피보나치 수의 합으로 유일하게 표현할 수 있습니다. 가령, $64 = 55 + 5 + 3 + 1$ 같은 표기법은 $5$와 $3$이 인접하게 됩니다. 이제 이 방식이 최소 개수의 항을 쓴 피보나치 합이라는것을 증명합시다.

 

Claim: 양의 정수를 최소 개수의 피보나치 수의 합으로 표현하는 방법은, Zeckendorf Representation이다.

Proof: 인접한 두 피보나치 수 $F_{N-1}$과 $F_N$이 있으면, 이 둘을 없애고 $F_{N+1}$을 추가하면 됩니다.

 

이제 최소 개수의 항을 쓴 피보나치 합(Zeckendorf Representation)과, 최대 개수의 항을 쓴 피보나치 합($1$을 $N$개 씀) 사이의 모든 개수의 피보나치 합으로 수를 표현할 수 있다는 것을 보입시다.

Proof: $F_N \ne 1$ 이 있으면, 이 수를 없애고 $F_{N-1}$과 $F_{N-2}$ 로 나누어서 피보나치 항의 개수를 $1$ 늘릴 수 있습니다. 이는 모든 피보나치 항이 $1$일 때까지 반복할 수 있습니다.

 

이제 Zeckendorf Representation을 만드는 법을 생각해보겠습니다. 이는 뺄 수 있는 가장 큰 피보나치 수를 greedy하게 빼면서 만들어 질 수 있습니다.

Proof: 위 greedy algorithm으로 인접하거나 유일하지 않은 두 수가 발생했다고 해봅시다. 문제가 되는 가장 큰 피보나치 수를 $F_N$이라고 해봅시다. $F_N + F_N, F_N + F_{N-1} \le F_{N+1}$ 이므로, 위 둘 대신 $F_{N+1}$이 greedy 알고리즘에서 추가되므로 모순입니다.

 

이제, 이 사실들을 잘 조합합시다. 결국, 우리는 $K$ 이상의 수 중에서 Zeckendorf Representation에서 $K$개 이하의 수를 사용하는 것 중 $N$번째 수를 찾으려고 합니다. Parametric Search를 이용하여 문제를 바꿔서, 특정한 수 미만의 수 중 Zeckendorf Representation에서 $K$개 이하의 수를 사용하는 수의 개수를 구합시다.

$0$ 이상 $M$ 미만의 수 중에서 Zeckendorf Representation에서 $i$개의 수를 사용하는 수의 개수를 $D_{M, i}$라고 합시다.

$M$ 미만의 가장 큰 피보나치수를 $F$ 라고 하면, $0$ 이상 $F$ 미만의 수는 $F$를 선택하지 않고, $F$ 이상 $M$ 미만의 수는 $F$를 선택합니다. 그 후, 해당 수들은 $0$ 이상 $M-F$미만의 수가 됩니다. 즉, $D_{M, i} = D_{F, i} + D_{M-F, i-1}$이 됩니다.

 

어떤 $D_X$ 를 구하고 싶을 때, $D_F$ 꼴인 수들을 memoization 한다면, 재귀적으로 $O(\log M)$ 번만의 step으로 피보나치수가 아닌 수들에 대한 $D$값을 구할 수 있습니다. 시간복잡도는 parametric과 Zeckendorf에서 사용된 $O(K \log MAX)$ 입니다.

 

코드: https://www.acmicpc.net/source/share/1da22eca99d94ec297042b48d7be9eea