[DP] 백준 9461 파도반 수열

#include <iostream>

using namespace std;

int d[101];

int main() {

       d[2]=d[3]=d[1] = 1;

       d[4] = d[5] = 2;

       

       for (int i = 6; i < 101; ++i) {

               d[i] = d[i - 1] + d[i - 5];

       }

       int t;

       cin >> t;

       while (t--) {

               int k;

               cin >> k;

               cout << d[k] << '\n';

       }

               

       return 0;

}

---

풀이

=> 1번 삼각형부터 차례대로 번호를 매기며 값을 나열해봤다. 

그 과정에서 6번째 삼각형은 5번째 삼각형의 변과 1번째 삼각형의 변으로 이루어져 있다는 것을 확인할 수 있었다.

그대로 점화식을 세우고 나열하였다.