[C/C++] 백준 9461번 - 파도반 수열(DP)

 

<코드>

#include<iostream> 
#include<stdio.h>
using namespace std;

long long DP[101];
int T, N;

int main()
{
	cin >> T;
	while (T--)
	{
		cin >> N;

		DP[1] = 1;
		DP[2] = 1;
		DP[3] = 1;

		for (int i = 4; i <= N; i++)
		{
			DP[i] = DP[i - 2] + DP[i - 3];
		}

		cout << DP[N] << "\n";
	}
	return 0;
}

점화식은 A[N] = A[N-2] + A[N-3] 인 것을 쉽게 찾을 수 있다. 그리고 N값이 79 이상일 경우 DP값이 int형의 범위를 넘어가버려서 왜 틀렸을까? 하면서 많이 헤맸다. DP의 자료형을 long long형으로 바꿔주면 정상 출력된다. 

 

www.acmicpc.net/problem/9461

9461번: 파도반 수열