(9461) 파도반 수열

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

단계별로 풀어보기

21단계(동적 계획법 1) 4번째

 

 

 

그림에서 길이가 7인 정삼각형부터 살펴보면, n번째 정삼각형의 길이는 n-1번째 정삼각형과 n-5번째 정삼각형의 길이의 합인 것을 알 수 있다. 그리고 계산해보면 길이가 3인 6번째 정삼각형부터 성립하는 것을 알 수 있어 P(N)= P(N-1)+P(N-5)이다.

또한 수열을 잘 살펴보면 P(N)= P(N-2)+P(N-3)라는 것을 직관적으로 알 수 있다. (이쪽 점화식이 조금 더 기본적이다.)

사실 점화식을 유도하는 증명을 찾아보면 조금 더 수학적이고 자세한 설명이 나오지만 지금은 크게 중요하진 않으므로 생략한다.

마지막으로 언제나 자료형 범위를 주의하자. P(100)은 int 범위를 벗어난다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  vector<long> dp(101);
  
  dp[1]= 1;  dp[2]= 1;  dp[3]= 1;
  
  for(int i=4;i<=100;i++)  dp[i]= dp[i-2]+dp[i-3];
  
  int T;
  
  cin >> T;
  
  while(T--){
    int n;
    
    cin >> n;
    
    cout << dp[n] << "\n";
  }
  
  return 0;
}