wxogus25   2년 전

제목 그대로 9009 피보나치 문제를 큰 수부터 선택하는 방식으로 풀었습니다.

그런데 어째서 이 문제가 그리디 알고리즘으로 풀리는지는 모르겠네요

그래서 나름대로 정당성(?)을 증명해보겠다고 몇번 끄적거리기는 했지만 결국 해내지 못했습니다...

수학고수님들 이 문제 좀 해결해주세요!

koosaga   2년 전

https://en.wikipedia.org/wiki/Zeckendorf%27s_theor... 

에 의하면 항상 두개의 연속한 피보나치 수를 포함하지 않는 유일한 표현 방법이 존재함을 증명할 수 있습니다. (증명 읽어보세요) 지금 사용하신 알고리즘이 저 표현방식을 반환합니다.

그렇다면, 저러한 표현 방식이 왜 최소 수를 사용할까요? 만약에 두개의 연속한 피보나치 수를 포함하는 방법이 더 최소라고 생각을 해보면, 그 두개의 연속한 수 Fi, Fi+1 을 묶어서 Fi+2로 줄일 수 있습니다. 최소라고 했음에도 그보다 더 효율적인 표현 방식을 찾았으니 가정에 모순이고, 즉 최소의 표현 방식은 두개의 연속한 피보나치 수를 포함하지 않습니다. 그러한 표현 방법은 위에서 언급했듯이 유일하게 존재합니다. 

wxogus25   2년 전

@koosaga

와.... 한번에 이해가 가는 설명이네요 그렇게 간단하게 증명할 수 있다니 감탄이 저절로 나오네요

감사합니다!

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