이번 문제는 점화식은 눈에 쉽게 보였지만 이유를 찾기 어려운 문제였다.
P(10)까지 첫 10개의 숫자는
이다. 사실 숫자를 보고 바로 규칙을 찾아버려서 어렵지는 않았지만 왜 그렇게 되는지 찾아보는데 많은 시간을 썼다.
일단 이 문제를 풀 수 있는 점화식은 두가지이다.
일단 그나마 쉽게 보이는 dp[N] = dp[N - 1] + dp[N - 5] 부터 확인해보자. 아래 P(6)까지 그려진 도형을 보면 6번째 삼각형이 5번째와 1번째 삼각형의 선분의 합을 빗변으로 가지는 것을 알 수 있다.
여기서 하나의 삼각형을 더 그려봐도 똑같은 규칙이 적용되는 것을 알 수 있다.
dp[N] = dp[N - 2] + dp[N - 3] 점화식은 어떤식으로 아래와 같은 형태로 증명이 가능하다.