마찬가지로 나이브하게 풀면 시간복잡도가 n번째 피보나치 수인 문제이다. 수열의 규칙성을 찾고, 규칙성으로 점화식을 세워 배열을 채워 나가거나, 탑다운 방식으로 재귀를 짜면 된다.

아래는 세 명의 코드이다.

1. 박정우(배열)

#include <bits/stdc++.h>
#define int long long
#define float long double
#define pp pair<int, int>
#define tp tuple<int, int, int>
#define mtp make_tuple
#define mp make_pair
using namespace std;
using lf = __float128;
using ld = __int128;
float pi = 3.141592653589793238462643383279502884197169399375105Q;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int ddx[8] = {0, 0, 1, -1, 1, 1, -1, 1}, ddy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    int t;
    cin >> t;
    int arr[111] = {0,1,1,1,2,2,3,4,5,7,9,};
    for (int i = 6; i <= 100; i++) {
        arr[i] = arr[i - 2] + arr[i - 3];
    }
    while (t--) {
        int n;
        cin >> n;
        cout << arr[n] << '\\n';
    }
    return 0;
}

2. 이하랑(재귀)

#include <stdio.h>
long long memo[110] = {0,};
long long pado(int n) {
	if (memo[n] != 0) return memo[n];

	if (n == 1) return 1;
	else if (n == 2) return 1;
	else if (n == 3) return 1;
	else {
		memo[n] = pado(n - 3) + pado(n - 2);
		return memo[n];
	}

}

int main() {

	int t;
	scanf("%d", &t);

	int n;
	for (int i = 0; i < t; i++) {
		scanf("%d", &n);
		printf("%lld\\n", pado(n));
	}

	
	return 0;
}

3. 정연우(재귀)

#include <stdio.h>

long long padoban(int n);
long long arr[110] = {0,};

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

    for(int i = 0; i<n; i++){
        scanf("%d", &num);
				printf("%lld\\n", padoban(num));
    }

}

long long padoban(int n){

    long long result = 0;

    if(arr[n] != 0){
        return arr[n];
    }

    if(n>=6){
        result += padoban(n-5);
        result += padoban(n-1);
        arr[n] = result;
        return result;
    }
    else if(n == 1 || n == 2 || n == 3){
        return 1;
    }
    else if(n == 4 || n == 5){
        return 2;
    }

    return 0;
}