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

초반 항들에는 전혀 규칙이 없는 것처럼 보인다.

하지만, 뒤로 갈수록 규칙성이 나타나는데, 매우 쉬우므로 설명은 생략.

C++ 코드(bottom-top)

#include <iostream>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long arr[101] = { 1,1,1,2,2 };

int main() {
	int T = 0;
	scanf("%d", &T);

	while (T--) {
		int n = 0;
		scanf("%d", &n);
		if (n < 5) printf("%lld\n", arr[n-1]);
		else {
			for (int i = 5; i < n; i++) {
				arr[i] = arr[i - 1] + arr[i - 5];
			}
			printf("%lld\n", arr[n - 1]);
		}
	}
}

C# 코드

using System.Text;
using System;
using static System.Console;

class Program
{
    static long[] arr = new long[101];
    public static void Main(string[] args)
    {
        arr[1] = 1; arr[2] = 1; arr[3] = 1; arr[4] = 2; arr[5] = 2;

        int T = int.Parse(ReadLine());
        for(int i = 0; i< T; i++)
        {
            int n = int.Parse(ReadLine());
            if (n < 6) WriteLine(arr[n]);
            else
            {
                for(int j = 6; j<= n; j++)
                {
                    arr[j] = arr[j - 1] + arr[j - 5];
                }
                WriteLine(arr[n]);
            }
        }

    }
}

Java 코드

import java.util.*;

public class Main {
    static long[] arr = new long[101];

    public static void main(String[] args) {
        arr[1] = 1; arr[2] = 1; arr[3] = 1; arr[4] = 2; arr[5] = 2;
        Scanner s = new Scanner(System.in);
        int T = s.nextInt();
        for(int i = 0; i<T; i++){
            int n = s.nextInt();
            if(n < 6) System.out.println(arr[n]);
            else{
                for(int j = 6; j<=n; j++){
                    arr[j] = arr[j-1] + arr[j-5];
                }
                System.out.println(arr[n]);
            }
        }

    }
}

Kotlin 코드

import java.util.*
import kotlin.math.*

fun main(args: Array<String>){
    val arr = LongArray(101)
    arr[1] = 1; arr[2] = 1; arr[3] = 1; arr[4] = 2; arr[5] = 2;
    val s = Scanner(System.`in`)
    val T = s.nextInt()
    for(i in 1..T){
        val n = s.nextInt()
        if(n < 6) println(arr[n])
        else{
            for(j in 6..n){
                arr[j] = arr[j-1] + arr[j-5];
            }
            println(arr[n])
        }

    }
}

Python 코드

arr = [0 for _ in range(101)]
arr[1] = 1; arr[2] = 1; arr[3] = 1; arr[4] = 2; arr[5] = 2;
T = int(input())
for i in range(T):
    n = int(input())
    if n < 6: print(arr[n])
    else:
        for j in range(6, n+1):
            arr[j] = arr[j-1] + arr[j-5]
        print(arr[n])