백준 9461번 : 파도반 수열

• 분류: 다이나믹 프로그래밍

코드

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    for(int i=0 ; i<T ; i++) {
        int n;
        cin >> n;
        long long result[100] = {1, 1, 1, 2, 2, };
        for(int j=5 ; j<n ; j++) {
            result[j] = result[j-1]+result[j-5];
        }
        cout << result[n-1] << '\n';
    }
}

• 코멘트
  
  f(n)=f(n-1)+f(n-5)의 점화식을 푸는 기초적인 다이나믹 프로그래밍 문제가 된다.
  주의할 부분은 f(100)이 엄청 커서 long long 으로 해 줘야 넉넉하다는 것.