본문 바로가기

Problem Solving/CodeUp

Well-Known Sequence

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

 

 

Well-Known Sequence

$f(n)=f(n-2)-f(n-1)$이라고 정의하자. 초항 $a$가 주어질 때, 적절한 두번째 항 $b$를 정하면 $f(n)$을 $0$으로 만들 수 있다. (단, $a \neq b$, $b$은 정수) 예) $a=25$, $b=15$인 경우, $25$, $15$, $10$, $5$, $5$, $

codeup.kr

 

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

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

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

 

힌트 1:

더보기

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

 

힌트 2:

더보기

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

 

힌트 3:

더보기

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

 

힌트 4:

더보기

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

 

힌트 5:

더보기

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

 

힌트 6:

더보기

구현은 당신의 몫입니다.

'Problem Solving > CodeUp' 카테고리의 다른 글

[CodeUp 4035] 커피전문점  (0) 2021.08.01
1,200  (0) 2021.06.27
1,000문제 달성  (2) 2021.02.15