[백준/DP/C++] 9461번 파도반 수열

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

9461번: 파도반 수열

처음에는 숫자 배열만 보고 p[n] = p[n-2] + p[n-3] 라고 생각했는데
직접 그림을 그려보니 p[n] = p[n-1] + p[n-5] 였다

그리고 어느순간 int의 범위를 벗어나서 배열은 long long 형으로 선언했다

#include <bits/stdc++.h>

using namespace std;
int tc;
long long a[101] ={0,1,1,1,2,2};

int main(void) {
    cin >> tc;

    for(int i=1; i<=tc; i++){
        int n;
        cin >> n;
        for(int j=6; j<=n; j++){
            a[j] = a[j-1] + a[j-5];
        }
        cout << a[n] << endl;
    }

    return 0;
}

반응형