[C++] BOJ 9461 파도반 수열

문제 출처

백준 온라인 저지

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

9461번: 파도반 수열

 

문제 

 

입 / 출력

 

풀이

1 1 1 2 2 3 4 5 7 9 의 규칙을 찾아서 점화식을 세운다

dp[i] = dp[i-3] + dp[i-2];

 

코드

#include <iostream>

using namespace std;

const int MAX = 101;
long long dp[MAX];
int T, n;

int main() {
  cin >> T;

  dp[1] = 1;
  dp[2] = 1;
  dp[3] = 1;
  for (int i = 4; i < MAX; i++) {
    dp[i] = dp[i - 3] + dp[i - 2];
  }
  for (int i = 0; i < T; i++) {
    cin >> n;
    cout << dp[n] << "\n";
  }
}