백준 2502번 : 떡 먹는 호랑이 in Python

2502번: 떡 먹는 호랑이

 

www.acmicpc.net

이 문제는 어제 받은 떡의 개수와 그저께 받은 떡의 개수를 더한 만큼의 떡을 먹는 호랑이에게 며칠 째에 몇 개의 떡을 주었는지가 입력으로 주어졌을 때 첫째 날과 둘째 날에 몇 개의 떡을 줬는지를 구하는 문제이다. 단, 문제의 답이 여러 개일 수 있지만 그 중 하나만 출력한다.

호랑이의 조건에서 알 수 있듯이 이 문제는 피보나치 수열의 D번째 항이 주어졌을 때 첫 번째 항과 두 번째 항을 구하는 문제이다. 가장 단순한 방법으로는 가능한 첫 번쨰 항과 두 번쨰 항을 생각해 그 경우에 대해 피보나치 수열을 구하고 특정 항이 원하는 항과 일치하는지를 일일이 보는 방법이 있다. 그러나 이 방법은 특정 항이 K일 때 피보나치 수열을 최대 K^2번 계산해야 하므로 이는 비효율적인 알고리즘이 될 것이다.

그래서 위 경우의 수를 줄이기 위해 피보나치 수열의 성질 하나를 증명한 뒤 이를 사용하려고 한다. 첫 번째 항과 두 번째 항이 i, j인 피보나치 수열 {a_n}과, 첫 번째 항과 두 번째 항이 모두 1인 피보나치 수열 {f_n}이 있다고 하자. 그러면 a_n = i * f_(n-2) + j * f_(n-1) 이 성립한다. 이는 수학적 귀납법으로 증명 가능하다. n = 3인 경우 a_3 = i * f_1 + j * f_2 = i + j이므로 성립하고, n = k일 때까지 성립한다고 가정하면 a_(n+1) = a_n + a_(n-1) = i * f_(n-2) + j * f_(n-1) + i * f_(n-3) + j * f_(n-2) = i * (f_(n-2) + f_(n-3)) + j * (f_(n-1) + f_(n-2)) = i * f_(n-1) + j * f_n이므로 n = k + 1일 때도 역시 성립한다. 따라서 수학적 귀납법에 따라 a_n = i * f_(n-2) + j * f_(n-1)이 성립한다.

따라서 첫 번쨰 항과 두 번쨰 항이 모두 1인 피보나치 수열을 먼저 구한 뒤 f_(D-2)와 f_(D-1)에 적절한 수를 곱해 K와 일치하는지를 확인하면 된다. 이렇게 하면 f_(D-2)와 f_(D-1)에 따라 가능한 첫 번째 항과 두 번째 항의 크기가 줄어들 수 있다. 즉, 가능한 첫 번쨰 항은 1~K/f_(D-2), 두 번째 항은 1~K/f_(D-1)로, f_(D-2)와 f_(D-1)에 대해서만 생각하면 된다. 게다가 피보나치 수열을 계산할 때 위에서 증명한 성질을 이용하면 한 번의 계산으로 피보나치 수열의 특정 항을 빠르게 계산할 수 있다. 

이를 코드로 구현하면 다음과 같다.

D, K = map(int, input().split())
# 첫 번째 항과 두 번째 항이 1인 피보나치 수열
Fibonacci = [0 for _ in range(D)]
Fibonacci[0] = 1
Fibonacci[1] = 1
for i in range(2, D):
    Fibonacci[i] = Fibonacci[i-1] + Fibonacci[i-2]
# 가능한 첫 번째 항과 두 번째 항의 범위
a = K//Fibonacci[D-3]
b = K//Fibonacci[D-2]
printed = False
for i in range(1, a+1):
    if printed:
        break
    for j in range(1, b+1):
        # 위에서 증명한 공식을 이용해 특정 항의 값과 어림잡은 값이 일치하는지를 판단한다.
        if K == i*Fibonacci[D-3] + j*Fibonacci[D-2]:
            print(i)
            print(j)
            printed = True
            break