[C/C++] BOJ 9461번 : 파도반 수열

1. 문제

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

2. 풀이

3. 답

1) 재귀로 풀기

#include <iostream>

using namespace std;
using ll = long long;
ll dp[102];

ll pado(ll N) {
    if (dp[N] != -1) return dp[N];
    if (N < 4)
        return dp[N] = 1;
    else if (N < 6)
        return dp[N] = 2;
    else
        return dp[N] = pado(N-1) + pado(N-5);
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        for (ll i = 0; i < 102; i++)
            dp[i] = -1;
        ll N;
        cin >> N;
        cout << pado(N) << endl;
    }

    return 0;
}

2) 반복문으로 풀기

#include <iostream>

using namespace std;
using ll = long long;

int main() {

    ll dp[102];
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 1;
    dp[4] = 2;

    for (ll i = 5; i < 102; i++) {
        dp[i] = dp[i-1] + dp[i-5];
    }

    int T;
    cin >> T;
    ll idx;

    while (T--) {        
        cin >> idx;
        cout << dp[idx] << endl;
    }
    return 0;
}