다이나믹프로그래밍1 - 백준 9461번 파도반 수열

www.acmicpc.net/problem/9461

9461번: 파도반 수열

IDEA 

스터디장님이 말하시길 DP는 점화식만 잘세워도 된다고 하셨다. 점화식의 기본은 일단 써보는 거라고 생각한다. 

1

1

1

2

2

3 = 1 + 2

4 = 1 + 3

5 = 1 + 4

7 = 2 + 5

9 = 2 + 7

12 = 3 + 9

16 = 4 + 12

6번째 부터 자기 자신-1 번째 수와 자신 -5 번째 수의 합으로 이루어지는 걸 확인할 수 있다. 

점화식을 세워보면  dp[n] = dp[n-1] + dp[n-5] (n >5) 이 된다. 

 

코드

#include <iostream>
using namespace std;

long long p[101] = {0};
int main() {
	p[1] = 1, p[2] = 1 ,p[3] = 1;
	p[4] = 2, p[5] = 2;
	int tc;
	scanf("%d", &tc);
	for (int i = 0; i < tc; i++) {
		int n;
		scanf("%d", &n);
		for (int i = 6; i <= n; i++) {
			p[i] = p[i - 1] + p[i - 5];
		}
		printf("%lld\n", p[n]);
	}
}