[백준][c++] 9461번: 파도반 수열

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

문제 해석

• 파도반 수열의 점화식을 보고 dp(동적 프로그래밍)으로 풀기

알고리즘 분류

• dp

풀이

• 그림을 보면 삼각형의 변의 길이가 늘어나는 규칙을 알 수 있음
• 이를 점화식으로 세우고 값을 한번에 계산하면 됨
• dp[i] = dp[i - 2] + dp[i - 3];

코드

#include <iostream>
#include <string>
#include <set>
using namespace std;

long long dp[101];
void solution() {
  int n;
  cin >> n;
  for(int i = 4; i <= n; i++) {
    dp[i] = dp[i - 2] + dp[i - 3];
  }
  cout << dp[n] << endl;
}

int main() { 
  dp[1] = 1;
  dp[2] = 1;
  dp[3] = 1;
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) solution();
}