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

 

알고리즘 분류: 수학, 다이나믹 프로그래밍

문제 링크: https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

 

【 풀이 】

 

동적계획법으로 해결 가능한 문제이다.

다른 DP 문제들과 마찬가지로 규칙을 찾아 점화식을 도출해 내는 것이 중요하다.

 

역시 규칙을 찾을 때까지 나열해보고 분석하면 된다.

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12

 

• P[1] = 1
• P[2] = 1
• P[3] = 1
• P[4] = P[1] + P[2] = 2
• P[5] = P[2] + P[3] = 2
• P[6] = P[3] + P[4] = 3
• ....
• 점화식: P[N] = P[N-3] + P[N-2] 

 

 

 

【 코드 】

 

#include<iostream>
using namespace std;

int main(void)
{
	long long int wave[101];
	wave[1] = 1; wave[2] = 1; wave[3] = 1;

	int t;
	cin >> t;
	for (int i = 1; i <= t; i++)
	{
		int n;
		cin >> n;
		for (int i = 4; i <= n; i++)
			wave[i] = wave[i - 3] + wave[i - 2];

		cout << wave[n]<<'\n';
	}
	return 0;
}