백준 9461

★★☆☆☆

지금까지 DP 문제를 풀때는 보통 n번째의 경우에서 하나 또는 두개를 분리해내서 일반항을 구하는 경우가 일반적이었는데 이문제는 결과들을 쭉 나열해서 규칙성을 찾는 방식이었다..
그 일반항에 어떤 규칙이나..이런것들은 딱히 없는것같아서 다소 허무했다
이게 맞다고,,?하는 느낌....
오답 처리가 되어도 억울하지않았는데 100번째 항을 넣어보니 overflow가 발생했길래 배열 타입을 longlong으로 바꿔주었다

<나의 풀이>

정말 11번째 항까지 쭉 나열해보았는데, 첫번째 항을 제외하고는 두번째 항부터는 더해지는 두 수의 간격이 4인 것을 발견했다.
그 결과, dp[n]=dp[n-1]+dp[n-5] 라는 점화식이 나왔다.

<다른 사람의 풀이>

너무 찝찝해서 새로운 방법을 찾아봤더니 다들 이렇게 푸시더라..
같은 방법으로, dp[n]=dp[n-2]+dp[n-3] 이라는 점화식도 나올 수 있다고 한다.

https://github.com/jeongopo/DaliyCodeCpp/commit/dd3387500f506665b6333ae39e37006c939cec9d