이런 문제는 결과값들을 분석하는 것이 중요하다고 생각한다. 그래서 결과값들을 써보며 분석해보았다. 결과값들을 저장하는 배열을 cnt라 하고, N을 index로 적용해서 생각했다.

• cnt[1] = 1 (1) 이다.
• cnt[2] = 2 (1+1, 2) 이다.
• cnt[3] = 4 (1+1+1, 1+2, 2+1, 3) 이다.
• cnt[4] = 7 (1+1+1+1, 1+1+2, ... , 3+1) 이다.
• cnt[5] = 13 (1+1+1+1+1, 1+1+1+2, ..., 3+2) 이다.
• 이 결과값들을 분석해보면 cnt[4]부터 다음과 같은 패턴을 가진다.
  -> cnt[i]=cnt[i-3]+cnt[i-2]+cnt[i-1].

Code

#include <iostream>
#define MAX 11
using namespace std;

int t, n;
int cnt[MAX];

void Input(){
    cin>>n;
}

int Solution(){
    cnt[0]=0;
    cnt[1]=1;
    cnt[2]=2;
    cnt[3]=4;
    for(int i=4; i<=n; i++){
        cnt[i]=cnt[i-3]+cnt[i-2]+cnt[i-1];
    }
    return cnt[n];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    for(int i=0; i<t; i++){
        Input();
        cout<<Solution()<<endl;
    }
    return 0;
}