[백준 BOJ][DP] 9461 파도반 수열

9461_파도반 수열

 

링크

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

 

풀이

 

그림으로 설명하겠습니다.

 

P1 = 1, P2 = 1, P3 = 1, P4 = 2, P5 = 2, P6 = 3, P7 = 4, P8 = 5, P9 = 7, P10 = 9

 

빨간색 3은 P6이고 구성은 P5 + P1입니다.

 

빨간색 4는 P7이고 구성은 P6 + P2입니다.

 

빨간색 12는 P10이고 구성은 P9 + P5입니다.

 

그렇다면 파도반 수열의 점화식을 구할 수 있습니다.

Pn = Pn-1 + Pn-5 (n >= 6)

 

DP를 이용해서 코드를 짜봅시다.

n은 100까지니 숫자가 커질 수 있습니다. long long으로 P[101]를 선언해야 합니다.

 

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

//9461_파도반 수열 #include <iostream> using namespace std;   long long P[101] = { 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 };   int main(){     int T, n;     int i;       cin >> T;       for (i = 11; i <= 100; ++i)         P[i] = P[i - 1] + P[i - 5];       for (i = 0; i < T; ++i){         cin >> n;         cout << P[n] << endl;     }       return 0; } Colored by Color Scripter

cs