9461 파도반 수열

n번째 파도반 수열을 구하는 문제이다.
파도반 수열은 나선의 가장 긴 선분을 한 변으로 정삼각형을 계속 그렸을 때, n번째 삼각형의 변의 길이를 나열한 것이다.
그러나 말로해도 잘 와닿지 않기 때문에 직접 세어보면 아래와 같다.
1 1 1 2 2 3 4 5 7 9 ...
대충보니 피보나치가 연상되는데, 숫자가 약간씩 다르다.
피보나치 수열은 f(n) = f(n-1) + f(n-2) 구조를 띠는데 반해
파도반 수열은 f(n) = f(n-2) + f(n-3) 의 구조를 띠는것을 볼 수 있다.
따라서 f(n) 을 담을 변수와 f(n-2),f(n-3) 을 담을 변수, 둘을 교환할 임시 변수 까지 4개의 변수가 필요하다. 그리고 상황에 맞게 swap 을 해주면 된다.

단, n>3 일 경우에만 위 점화식이 성립하는것에 유의하자.

 소스