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

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

9461번: 파도반 수열

소스 코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int N;
	vector<long long int> P(101);
	cin >> N;
	P[1] = 1;
	P[2] = 1;
	P[3] = 1;
	for (int i = 4; i <= 100; i++)
		P[i] = P[i - 2] + P[i - 3];

	while (N != 0)
	{
		int num;
		cin >> num;
		cout << P[num] << '\n';
		N--;
	}
}

마무리 : 수학 문제로 dp로 풀어본 결과 소스 코드에 나와 있는 계산식으로 답을 나올 수 있었다. 대신에 값이 크기 때문에 자료형 long long int로 만들어줘야한다. 그렇지 않으면 틀린다고 나온다.