Well-Known Sequence

약 일주일 전에 코드업에서 오랫동안 고민하던 문제를 풀었는데, 바로 이 문제다.

 

Well-Known Sequence

 

매우 정수론 같이 생겼지만, 아이디어가 잘 떠오르지 않는다... 예제만으로 규칙을 찾기는 쉽지 않고, 수열의 길이를 가장 길게 만들라는 문장도 잘 와 닿지 않는다. 이 문제를 풀기 위해서는... 내가 몇 달 동안 생각하지 못했던 '발상의 전환'이 필요하다!

이런 부류의 아이디어성 문제는 아이디어 자체를 생각하는 과정도 재미있고, 또 내가 생각한 아이디어가 맞았을 때 엄청난 희열을 느낄 수 있다..! 그러니 가능하다면 혼자 고민하며 문제를 즐기는 시간을 가지도록 하자.

아래는 내 생각의 흐름이자 힌트이다. 정 안 풀린다 싶으면 위에서부터 하나씩 참고해도 나쁘지 않을 것 같다.

 

힌트 1:

아래 게시판에도 나와있듯이, 이 문제의 제목은 '유명한 수열'입니다.

 

힌트 2:

수열이 끝나기 직전 상황을 봅시다. ... X, X, 0 꼴로 끝이 나죠. 이를 이용해 수열을 복원해봅시다.

 

힌트 3:

복원한 수열은 피보나치 수열과 유사합니다. 정확히 말하면, 피보나치 수열의 각 항에 같은 수를 곱해준 꼴입니다.

 

힌트 4:

힌트 3에 의해 초항 a는 어떤 피보나치 수의 배수여야 합니다.

 

힌트 5:

수열의 길이를 가장 길게 만들려면 a를 나누는 피보나치 수 중 가장 큰 수를 찾아야 합니다.

 

힌트 6:

구현은 당신의 몫입니다.