파이썬) 백준 알고리즘 | 10327번 : 피보나치 문제해결전략

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

10327번: 피보나치 문제해결전략

풀이

먼저 가보나치 수열의 일반항을 구해보겠습니다.

$$ G(3) = G(1) + G(2) $$

$$ G(4) = G(2) + G(3) = G(1) + 2G(2) $$

$$ G(5) = G(3) + G(4) = 2G(1) + 3G(2) $$

$$ G(6) = G(4) + G(5) = 3G(1) + 5G(2) $$

$$ G(7) = G(5) + G(6) = 5G(1) + 8G(2) $$

$$ G(n) = G(n-1) + G(n-2) = F(n-2)G(1) + F(n-1)G(2) $$

이렇게 유도할 수 있습니다.

 

이 상황에서 ax+by=c (a=F(n-2), b=F(n-1), c=G(n), x=G(1), y=G(2))라는 식으로 나타낼 수 있는데

a, b, c가 주어지므로 주어진 식을 만족하는 x, y 집합 중에서 

$$  x \le y,        y가 최소 $$

이 조건을 만족하는 x, y가 답이 됩니다. 

 

t = int(input())
for _ in range(t):
    n = int(input())
    fibo = [1,1]
    while fibo[-1] < 10**9:
        fibo.append(fibo[-1]+fibo[-2])
    check = False
    ans = []
    for i in range(44,0,-1):
        a = 1
        while a*fibo[i-1]+fibo[i] <= n:
            if (n - a*fibo[i-1]) % fibo[i] == 0:
                b = (n - a*fibo[i-1]) // fibo[i]
                if a <= b:
                    ans.append([a,b])
            a += 1
        if len(ans) > 10:
            break
    ans.sort(key = lambda x : x[1])
    print(*ans[0])