나무 숲

파도반 수열 Padovan sequence 1, 1, 1, 2, 2, 3, 4, 5, 7, 9... 위 그림과 수열로 구성된 문제가 국내 ACM 문제 중 하나로 나왔었습니다. 그림, 수열을 참고하여 정수 n을 입력했을 때 n번째 값을 출력하는 내용입니다. 수열의 초기값과 점화식을 알고 있으면 아아아주 쉽게 풀 수 있지만 그림과 수열로 유추하실 수 있으면 더 좋겠습니다! 파도반 수열이란?? Richard Padovan에 의해 이름붙었습니다. 위 그림은 파도반 수열을 표현하는 그림 중 하나입니다. 각 삼각형은 한 변을 두 개의 다른 삼각형과 공유하는데요, 초기값 P(0)~P(2)를 제외하고 P(n) = P(n-2) + P(n-3)임을 알 수 있습니다. * 초기값이 P(0) = P(1) = P(2) = 1인 ..