[백준][DP] 9461 : 파도반 수열

문제

https://www.acmicpc.net/problem/9461

필요 지식

 - dynamic programming

해결 방법

 - 이런 수열 문제는 실제로 순서대로 해보며 규칙 발견하는 것이 좋다.

 - 백준에서 이미 처음 수열을 (1,1,1,2,2,3,4,5,7,9)로 주어졌음. 그 이후 부터 시작

 - N = 11 : 3 + 9 = 12

 - N = 12 : 4 + 12 = 16

 - N = 13 : 5 + 16 = 21

 - 규칙 발견

     - N[n] = N[n-1] + N[n-5]

주의할 점

 - 메모리 생각

• 특히 DP같은 문제에서 더해가다가 숫자가 굉장히 커질 수 있으므로,
• int같은 작은 범위 가지는 변수말고, long long등을 지정해야함

코드