2023-10-10-padovan-9461

• toc {:toc}

문제 확인하기

풀이

주어진 그림에서 몇 개 더 생각해봤더니 규칙이 보였다. N이 5일 때까지는 11122로 연속되지만 N이 6이상일 때는 N-1의 변의 길이와 N-5의 변의 길이의 합으로 이루어진다. 항상 마지막으로는 길이가 자료형을 뛰어넘는 지를 확인한다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
 
long long dp[103] = {0,};
 
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
 
    int T;
    cin >> T;
 
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 1;
    dp[4] = 2;
    dp[5] = 2;
    while(T--){
        int N;
        cin >> N;
 
        if(N <= 5){
            cout << dp[N] << endl;
            continue;
        }
        for(int i = 6; i <= N; i++){
            dp[i] = dp[i-1] + dp[i-5];
        }
        cout << dp[N] << endl;
    }
 
    return 0;
}