(SWEA c++)3376. 파도반 수열

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWD3Y27q3QIDFAUZ&categoryId=AWD3Y27q3QIDFAUZ&categoryType=CODE

SW Expert Academy

문제를 보면 규칙을 찾을 수 있다.

P[i] = P[i - 3] + P[i - 2]의 규칙이 보인다.

DP를 이용하여 미리 배열에 Pn을 모두 저장해 놓은다.

N <= 100 이므로 간단하게 구현할 수 있다.

#include <iostream>

using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long P[101] = {0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9};
    int t;
    
    cin >> t;
    
    for(int i = 11; i <= 100; i++)
        P[i] = P[i - 3] + P[i - 2];
     
    for(int tc = 1; tc <= t; tc++)
    {
        int n;
        cin >> n;
        
        cout << "#" << tc << " " << P[n] << endl;
    }
    return 0;
}