(19) [C++, Java] 백준 No.9461 : 파도반 수열

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-20-DP-문제-풀이4-3-백준-No9461-파도반-수열

 

# C++

/*방법1*/
#include <iostream>

using namespace std;

long long d[101];

int main()
{
    int T;
    cin >> T;

    while(T--){
        int n;
        cin >> n;

        d[1] = 1;
        d[2] = 1;
        d[3] = 1;
        d[4] = 2;
        d[5] = 2;

        for (int i = 6; i <= n; i++)
            d[i] = d[i - 1] + d[i - 5];

        cout << d[n] << "\n";
    }
}

/*방법2*/
#include <iostream>

using namespace std;

long long d[101];

int main()
{
    int T;
    cin >> T;

    while(T--){
        int n;
        cin >> n;

        d[1] = 1;
        d[2] = 1;
        d[3] = 1;

        for (int i = 4; i <= n; i++)
            d[i] = d[i - 2] + d[i - 3];

        cout << d[n] << "\n";
    }
}

# Java

import java.util.*;
import java.math.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        long[] d = {0,1,1,1,2,2,3,4,5,7,9};
        d = Arrays.copyOf(d, 101);
        for (int i=10; i<=100; i++) {
            d[i] = d[i-1] + d[i-5];
        }
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            System.out.println(d[n]);
        }
    }
}