Baekjoon 9461번 파도반 수열

문제

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

걸린 시간

00 : 37 : 35

풀이

C++

#include <stdio.h>
#include <iostream>
using namespace std;

int N;
int count = 5;
long long cache[100] = {1, 1, 1, 2, 2};

long long padovan(int n){
    // 메모이제이션
    auto& ret = cache[n-1];
    if(ret != 0)
        return ret;
    // 구해진 수열 부터 n번째 까지
    for(int i = count; i < n; i++){
        cache[i] = cache[i-1] + cache[i-5];
        count++;
    }
    return cache[n-1];
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &N);
        printf("%lld\n", padovan(N));
    }
    return 0;
}

P(5) 까지는 1, 1, 1, 2, 2 로 일정하다. P(6) 부터는 P(n-1) + P(n-5) 를 따른다.

예) P(6) = P(5)+P(1), P(7) = P(6)+P(2)

n 값이 커지면 수열의 크기가 int의 범위를 벗어나게 된다. long long 자료형을 사용해야 된다.