파도반 수열 (백준 - 9461번)

동적계획법을 사용하는 문제였다.

 

우선 점화식을 찾기 위해 규칙이 어떠한지 부터 살펴보자.

 

P(1)~P(3)일때는 1로 모두 동일하다.

그리고 P(4)~P(5)일때 2이다. 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] 

 

결과값이 int의 범위를 넘어가기 때문에 P(N)의 값을 저장할 dp 테이블 배열을 long long 형식으로 선언해주어야 한다.

 

코드는 다음과 같다.

#include <iostream>
using namespace std;

int main()
{
	long long dp[100 + 1];
	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 1;
	for (int i = 3; i <= 100; ++i)
	{
		dp[i] = dp[i - 2] + dp[i - 3];
	}

	int input;
	cin >> input;
	int* c = new int[input];
	for (int i = 0; i < input; ++i)
	{
		cin >> c[i];
	}

	for (int i = 0; i < input; ++i)
	{
		cout << dp[c[i]] << endl;
	}
}