#9461번 파도반 수열 (C++)

9번째 파도반(x)부터는 

f(x) = f(x-5) + f(x-1)이라는 점화식을 발견했다.

쉽다고 생각해서 풀었으나 단칼에 오답이 나왔고, 

아니나 다를까 타입 선언에서 흔한 실수를 저질러 버렸다 (int가 아닌 long long이어야 한다)

 

1. 동적할당 재귀버젼

#include <iostream>
using namespace std;

long long arr[101] = {0,1,1,1,2,2,3,4,5};
int T;

long long find(int a){
    if(a<=8) return arr[a];
    else if(a>8&&arr[a]) return arr[a];
    else return arr[a] = find(a-1) + find(a-5);
}

void input(){
    cin >> T;
    for(int i=0; i<T; i++){
        int tem = 0;
        cin >> tem;
        cout << find(tem) << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    input();

    return 0;
}

 

2. 동적할당 반복문(for) 버젼

#include <iostream>
using namespace std;

long long arr[102] = {0,1,1,1,2,2,3,4,5,};
int T;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for(int i=9; i<101; i++){
        arr[i] = arr[i-1] + arr[i-5];
    }

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

    return 0;
}

위의 정답 - 재귀 / 아래의 정답 for문

둘다 속도는 0ms로 나온다.