🐣 문제

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

🐥 코드

#include <iostream>
using namespace std;
long long DP[101];
long long dp(int n){
  if(DP[n] > 0) return DP[n];
  if(n == 1 || n == 2 || n == 3) return 1;
  else return DP[n] = dp(n-3) + dp(n-2);
}

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

  for(int i = 0; i < N; i++){
    int tmp;
    cin >> tmp;
    cout << dp(tmp) << '\n';
  }
}

//Top-Down

#include <iostream>
using namespace std;
long long DP[101];

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

  for(int i = 0; i < N; i++){
    int tmp;
    cin >> tmp;
    DP[1] = DP[2] = DP[3] = 1;
    for(int j = 4; j <= tmp; j++){
      DP[j] = DP[j-2] + DP[j-3];
    } 
    cout << DP[tmp] << '\n';
  }
}

//Bottom-UP