ryan_park   2년 전

아래와 같은 방법으로 이 문제를 해결하였는데요.


아래와 방법으로 하였을 때 시간복잡도를 어떻게 예측해야 되는지 궁금합니다.

최악의 경우에는 K^2의 경우가 나올 것 같은데, 명확하지가 않은 것 같아 질문을 드립니다.

chogahui05   2년 전

넘어온 날을 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



chogahui05   2년 전

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

ax + by = k꼴이잖아요.

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


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

ryan_park   2년 전

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

감사합니다 :)

댓글을 작성하려면 로그인해야 합니다.