넘어온 날을 D, 그 날 준 떡의 갯수가 K네요. 허허.. 일단 O(k^2)이긴 합니다..

일단 일반식은 Fibo(D-3)*i + Fibo(D-2)*j = k일 때 빠져나오면 되는 거고요.

하. 이거 조금 어렵네요.

사실 저런식으로 짜면 최악의 경우에 O(k*Fibo(D-2)) 즈음 나올텐데요.

일단 Fibo(D-2)와 Fibo(D-3)의 gcd는 1이 나오고요. 보나마나. 그럴 거에요. 재귀적으로

gcd(a, b) = gcd(b, a%b)로 정의되는데요.

피보나치의 일반항이 f(n) = f(n-1) +f(n-2)로 정의되기 때문에

gcd(f(n),f(n-1)) = gcd(f(n-1), f(n-2)) = gcd(f(n-2), f(n-3)) = ... = gcd(2,1) = 1

이래 되죠.

당장 아래 두 수식을 비교해 보면 왜 Fibo(D-2)만치 돌아야 하는지 아실 수 있으실 거에요.

f(d-3)*i + f(d-2)*j

f(d-3)*(i+f(d-2)) + f(d-2)*j

이걸 해결하는 방법 중 하나는..

ax + by = k꼴이잖아요.

이걸 k-ax = by 이렇게 변형시킬 수 있습니다.

요걸 조건식으로 잘 따지시면 O(k^2)를 O(k)로 줄일 수 있습니다.

아...그렇게 푸는게 좀더 명확한 해법인 것 같네요!

감사합니다 :)