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

 

다이나믹 프로그래밍 문제입니다.

 

파도반 수열 n길이에서 n번째 수를 찾는 문제입니다.

파도반 수열 첫 10개의 숫자는

1, 1, 1, 2, 2, 3, 4, 5, 7, 9입니다.

여기서 6번째 자리숫자부터는

현재위치 전의 값 + 현재위치 -5번째의 값을 더한 값이 나옵니다.

 

이를 코드로 하면

DP[i] = DP[i-1] + DP[i-5]

 

#include <iostream>
using namespace std;

int main(int argc, char *argv[])
{
   int n;
   int len;
   long long int DP[110] = { 0, };
   cin >> n;

   DP[1] = 1;
   DP[2] = 1;
   DP[3] = 1;
   DP[4] = 2;
   DP[5] = 2;

   while (n-- > 0) {
      cin >> len;
      
      if (DP[len] != 0) {
         cout << DP[len] << endl;
         continue;
      }
      for (int i = 6; i <= len; ++i) {
         DP[i] = DP[i - 1] + DP[i - 5];
      }
      cout << DP[len] << endl;
   }
   return 0;
}