[백준 9461번] [동적 계획법] 파도반 수열

접근 방법

계속해서 이전 값들을 더해나가는 경향성 자체를 몇 번 시도하다보면 쉽게 파악할 수 있다.

또한 더하는 숫자들의 기준이 반복되는 것을 통해 점화식으로 이 문제를 쉽게 해결할 수 있음을 파악할 수 있다.

 

이전 포스트에서도 계속 언급한 것처럼 점화식 형태로 표현되는 것들은 일반적으로 DP를 활용해서 풀어줄 수 있다.

 

코드

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef long long ll;

int main(void){
    fastio;
    ll dp[101];
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 1;
    dp[4] = 2;
    dp[5] = 2;
    dp[6] = 3;
    dp[7] = 4;

    for(int i = 8; i <= 100; i++){
        dp[i] = dp[i - 1] + dp[i - 5];
    }

    int n;
    cin >> n;
    for(int i = 0; i < n ; i++){
        int t;
        cin >> t;
        cout << dp[t] << "\n";
    }

    return 0;
}