제켄도르프 분해 응용 - 정수를 피보나치 수의 합과 차로 표현하기

1. 문제

 

8229번: Fibonacci Representation (acmicpc.net)

8229번: Fibonacci Representation

 

2. 풀이

 

어떤 정수를 최소 개수의 피보나치 수만을 사용해서 합과 차로 표현하는 문제

 

중복해서 사용가능하다.

 

제켄도르프 분해에 의하면 모든 자연수는 연속하지 않은 피보나치 수들의 합으로 유일하게 표현할 수 있다

 

https://deepdata.tistory.com/867

피보나치 수열 심화과정3 -모든 자연수는 피보나치 수의 합으로 유일하게 분해할 수 있다(제켄도

 

여기는 합만 있지 차는 없어서 문제가 조금 까다롭다..

 

그렇지만 제켄도르프 분해를 하는 방법을 떠올려보면 무조건 어떤 정수보다 작거나 같은 가장 큰 피보나치 수를 빼나가는 방식으로 했는데..

 

이를 이용해서 최대 정수인 $4*10^{17}$정도에 가장 가까운 피보나치 수는 86번째 피보나치 수라는 것을 알고

 

$$F_{86} = 420196140727489673$$

 

1) 가장 큰 피보나치 수부터 거꾸로 순회해서 처음으로 n보다 작아지는 피보나치 수 $F_{i}$를 찾으면 

 

$F_{i+1}$은 n보다 큰 수이고 $F_{i}$는 n보다 작은 수가 된다.

 

2) 이 때 두 수와 n의 차이 $F_{i+1} - n$와 $n - F_{i}$를 비교해서.. 차이가 더 작다면 그것을 n으로 대체하는게 유리하다.

 

왜냐하면 결국 n을 0으로 만들어야하기 때문인데.. 차이가 커질수록 더 많은 피보나치 수를 사용해야하기 때문이다.

 

즉 $F_{i+1} - n >= n - F_{i}$이면 $n = n - F_{i}$이지만 $F_{i+1} - n < n - F_{i}$이면 $n = F_{i+1} - n$으로 갱신한다.

 

여기서 핵심은 더 큰 $F_{i+1}$을 써야한다면, $n = n - F_{i+1}$이 아니라 $n = F_{i+1} - n$으로 해줘야한다.

 

실제 표현을 구하는게 아니라 몇개를 써야하는지만 중요하다

 

+ 제켄도르프 분해에 의하면 모든 자연수 n은 피보나치 수의 합으로 표현할 수 있으므로 양수로 만든 n은 반드시 0이 될 수 밖에 없다.

 

from sys import stdin

#fibonacci representation
def representation(n):
    
    count = 0 #피보나치 수를 사용한 수
    
    while n:
        
        #가장 큰 피보나치 수부터 거꾸로 순회하여...
        for i in range(86,-1,-1):
            
            if f[i] == n: #만약 n과 피보나치 수가 동일하다면 그걸 쓰면 끝이니까 count+1을 바로 return
                
                count += 1

                return count
            
            #처음으로 n보다 작아지는 피보나치 수 f[i]를 구함
            elif f[i] < n:
                
                break
        
        #그러면 f[i+1]은 n보다 크고 f[i]는 n보다 작다
        large = f[i+1]
        small = f[i]
        
        #이때 n과 거리 차이가 작은 수를 사용함
        #여기서 large를 써야한다면, n = n - large로 음수가 아니라 n = large - n으로 양수를 사용
        #제켄도르프 분해에 의하면 모든 양의 정수 n은 연속하지 않은 피보나치 수의 합으로 표현할 수 있다
        if (large - n) >= (n - small):
            
            n -= small
            count += 1
        
        else:
            
            n = large - n
            count += 1
    
    return count

#4*10^17에 가장 가까운 F86 = 420196140727489673
f = [0,1,1]

for i in range(3,87):
    
    f.append(f[i-1]+f[i-2])

p = int(stdin.readline())

for _ in range(p):
    
    n = int(stdin.readline())

    print(representation(n))