9461 파도반 수열

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, ... 처럼 나열했을 때, 이전 두 번째와 세 번째 수의 합이 다음 수가 된다는 것을 유추해볼 수 있습니다.

• P(N) = P(N - 2) + P(N - 3)임을 이용해서 바로 재귀를 사용하게 되면 함수 호출이 매우 많아져 (N = 100의 경우 약 2^100) 메모리 혹은 시간 초과가 발생할 수 있습니다. 손으로 계산하듯이 풀면 훨씬 빠르게 풀 수 있습니다.

• P(100)은 int형의 범위를 넘어갑니다.

점화식의 증명

N > 5에서, P(N) = P(N - 1) + P(N - 5)임은 정의에 의해서 알 수 있습니다.

수학적 귀납법을 사용하면 P(N) = P(N - 2) + P(N - 3)임을 쉽게 증명할 수 있습니다.

P(4) = P(2) + P(1)이고, 4 <= k <= N인 모든 k에 대해서 P(k) = P(k - 2) + P(k - 3)이라면,

P(N + 1) = P(N) + P(N - 4)

= P(N - 2) + P(N - 3) + P(N - 4)

= P(N - 1) + P(N - 2)

따라서, 모든 N에 대해서 P(N) = P(N - 2) + P(N - 3)입니다.