[BOJ 8229] Fibonacci Representation

기분 좋게 풀어서 포스팅 해보겠습니다.

 

https://www.acmicpc.net/problem/8229

8229번: Fibonacci Representation

특정 수 $n$이 주어졌을 때 $n$을 피보나치 수들의 합과 차로 표현할 때 필요한 피보나치 수의 개수를 묻는 문제입니다.

보자마자 dp가 생각나는 문제입니다. 실제로 dp로 AC를 받은 사람들이 많고 시간도 굉장히 여유로웠습니다. 보통 이런 문제의 경우, 보자마자 생각없이 dp를 짠 후 열심히 디버깅을 하다 AC를 받게 됩니다. 하지만 어쩌다 보니 고민할 시간이 너무 많이 주어졌고 dp에 확신이 없던 나머지 일반해를 찾아서 문제를 풀어버렸습니다.

 

 

$F_{0}=1$, $F_{1}=1$, $F_{i}=F_{i-1}+F_{i-2}$로 피보나치 수열을 정의 하고,

$f(n)$을 $n$을 표현하기 위해 필요한 피보나치 수의 최소 개수로 정의 하겠습니다. $f(n)$이 잘 정의 되는 것은 생략하겠습니다.

 

Claim.

($i>4$) $F_{i-1}<n<F_{i}$일 때,

$n<F_{i}+F_{i-4}$     ->      $f(n)=1+f(n-F_{i})$

$n=F_{i}+F_{i-4}$     ->      $f(n)=2$

$n>F_{i}+F_{i-4}$     ->      $f(n)=1+f(F_{i+1}-n)$

 

$n$의 범위에 따라 어떻게 표현해야 개수를 최소로 할 수 있는지 직접 알려주는 점화식입니다.

$F_{i-1}$과 $F_{i}$사이에는 길이 $F_{i-2}$의 구간이 있습니다. 이 구간을 다시 $F_{i-4}$와 $F_{i-3}$의 구간으로 나누어 $F_{i-1}$로 표현할지 $F_{i}$로 표현할지 결정해주는 방식입니다. 증명해보도록 하겠습니다.

 

Lemma1.
$n$을 인덱스의 차이가 3이상인 피보나치 수 $f(n)$개의 합으로 나타낼 수 있다.

증명)
$n=\sum_{i=1}^{f(n)} (-1)^{t_{i}} F_{a_{i}}$    ($a_{1} \leq a_{2}\leq .... \leq a_{f(n)}$)
와 같이 표현했을 때, $a_{i}+3 \leq a_{i+1}$가 성립하게 a_{i}들을 잡을 수 있다는 뜻이다. $n$을 $f(n)$개의 피보나치 수의 합으로 표현하는 방법이 여러개 있을 수 있는데, 그 중에서 인덱스의 제곱합이 최대인 것을 잡자. $\sum a_{i}^2$가 최대인 $\{a_{i}\}$ 순서쌍을 잡은 것이다.

이 때 $a_{i}+3>a_{i+1}$이라면

1)$a_{i}=a_{i+1}$
$F_{x}-F_{x}=null$
$F_{x}+F_{x}=F_{x+2}-f_{x-1}$

2)$a_{i}+1=a_{i+1}$
$F_{x+1}+F_{x}=F_{x+2}$
$F_{x+1}-F_{x}=F_{x-1}$

3)$a_{i}+2=a_{i+1}$
$F_{x+2}+F_{x}=F_{x+3}-F_{x-1}$
$F_{x+2}-F_{x}=F_{x+1}$

로 모든 경우 모순이다.

 

Lemma2.
$F_{x}+F_{x-3}+F_{x-6}+....<F_{x+1}$
증명 생략

 

이제 $F_{k-1}<n<F_{k}$을 피보나치 수들의 합으로 표현하는 방법들을 생각해보습니다. 그 중 인덱스의 제곱합이 최대인 것 아래와 같이 하나 잡겠습니다. Lemma1에서 보였듯이 $a_{i}$와 $a_{i+1}$의 차이가 3이상이어야 합니다.

$n=\sum_{i=1}^{f(n)} (-1)^{t_{i}} F_{a_{i}}$    ($a_{1}<a_{2}<....a_{f(n)}$)

 

만약 $a_{f(n)}>k$라면 $F_{x}-( F_{x-3}+F_{x-6}+....)>F_{x}-F_{x-2}=F_{x-1}$이기 때문에 모순입니다.

마찬가지로 $a_{f(n)}<k-1$라면 $F_{x}+F_{x-3}+....<F_{x+1}$이기 때문에 모순입니다.

따라서 $a_{f(n)}$, 즉 가장 큰 피보나치 수는 $F_{k-1}$ 또는 $F_{k}$여야 된다는 것을 알 수 있습니다.

 

case1) $n=F_{k-1}+F_{k-4}$

두 개의 합차로 표현가능하지만 한개의 합차로 표현 불가능하기 때문에 $f(n)=2$인 것을 알 수 있습니다.

 

case2) $n<F_{k-1}+F_{k-4}$

만약 $a_{f(n)}=k$라면 나머지 부분으로 $F_{k}-n>F_{k}-F{k-1}-F_{k-4}=F_{k-3}$을 표현해야 합니다.

Lemma2에 의해 $F_{k-3}$보다 작은 수들로는 표현이 불가능한 것을 알 수 있습니다. 따라서 두번째로 큰 피보나치 수의 인덱스 $a_{f(n)-1}$은 $k-3$이 되어야 합니다.

이 때 $F_{k}-F_{k-3}=F_{k-1}+F_{k-4}$이므로 $F_(k-1)$을 포함한 $f(n)$개의 피보나치 수의 합으로 $n$을 표현할 수 있다는 것을 알 수 있습니다. $n$에서 $F_{k-1}$을 뺀 수는 f(n)-1개의 피보나치 수의 합차로 표현 될텐데 이 또한 최소 개수를 이용해야 하므로 $f(n-F_{k-1})=f(n)-1$인 것을 알 수 있습니다.

$a_{f(n)}=k-1$이라면 마찬가지로 $f(n)=f(n-F_{k-1})+1$인 것을 바로 알 수 있습니다.

 

case3) $n>F_{k-1}+F_{k-4}$

case2와 마찬가지 방법으로 해결할 수 있습니다. 만약 제일 큰 항이 $F_{k-1}$이라면 $F_{k-4}$도 포함해야 하므로 $F_{k-1}+F_{k-4}=F_{k}-F_{k-3}$을 이용해 $F_{k}$를 포함하도록 바꿀 수 있고 따라서 $f(n)=f(F_{k}-n)+1$이 됩니다.

 

 

따라서 claim이 증명됩니다. 이 클레임을 이용하면 아래와 같은 코드로 가볍게 문제를 해결할 수 있습니다.

 

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <set>

#define sz(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int INF = 0x3c3c3c3c;
const ll LINF = 1ll*INF*INF*2;

const int N = 1000001;
int n;
ll m;
ll P[100];
void make() {
	P[0]=1; P[1]=1;
	for(int i=2; i<90; i++) P[i]=P[i-1]+P[i-2];
}

int f(ll x) {
	if(x==4) return 2;
	int idx=lower_bound(P+1, P+86, x)-P;
	if(P[idx]==x) return 1;
    
	//P[idx-1]<x<P[idx];
	if(x==P[idx-1]+P[idx-4]) return 2;
	if(x<P[idx-1]+P[idx-4]) return f(x-P[idx-1])+1;
	else return f(P[idx]-x)+1;

}
int main(void) {
	make();
	scanf("%d", &n);
	for(int i=0; i<n; i++) {
		scanf("%lld", &m);
		printf("%d\n", f(m));
	}
}