시작

우선 이 문제는 잘 생각해보면, 어느 수열의 개수와 비슷하게 볼 수 있다. 우선 한번 1부터 3까지의 값만 한번 구해보도록 하자

1

• 1
  1개

2

• 1 + 1
• 2
  2개

3

• 1 + 1 + 1
• 1 + 2
• 2 + 1
• 3
  4개

이렇게 3까지의 개수를 구해보았는데, 한번 4의 개수(n)와 한번 비교를 해보자 4의 개수는 7개라고 한다. 그렇다면 이 수열과 한번 비교를 해보자면, n = f(3) + f(2) + f(1)과 같다. 그렇다면 미지수로 표현을 해보자면 n = f(n-1) + f(n-2) + f(n-3)이라는 점화식이 나온다. 그렇다면 한번 문제를 풀어 보도록 하자. 점화식만 보면 피보나치 수열과 비슷한 모습을 보이게 된다.

코드

#include<iostream>
#include<string>
#include <vector>
#include <algorithm>
#include<map>
#define toChar '0'

using namespace std;

int memo[12];

int fibo(int n) {
    if (n < 0) return 0;
    if (n == 0) return 1;
    if (n == 1) return 1;
    if (memo[n]) return memo[n];
    return memo[n] = fibo(n - 1) + fibo(n - 2) + fibo(n - 3);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n, temp;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        cout << fibo(temp) << "\n";
    }
}