[ 백준 ] 9461번 - 파도반 수열 (C++)

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

9461번: 파도반 수열

 

 

[ 문제풀이 ]

 

1. dp [ i ] = dp [ i - 1 ] + dp [ i - 5 ]의 점화식을 이용하여 문제를 풉니다.

 

2. 숫자의 범위가 int를 벗어나기 때문에 long long 자료형을 써줍니다.

 

[ 소스코드 ]

#include<iostream>
 
using namespace std;
 
int main()
{
    int T;
    scanf("%d", &T);
    long long arr[101] = { 0 };
 
    arr[1] = arr[2] = arr[3] = 1;
    arr[4] = arr[5] = 2;
 
    for (int i = 6; i <= 100; i++) {
        arr[i] = arr[i - 1] + arr[i - 5];
    }
 
    for (int t = 0; t < T; t++) {
        int N;
        scanf("%d", &N);
 
        printf("%lld\n", arr[N]);
    }
}