[백준 C++] 9461 파도반 수열 - 다이나믹프로그래밍

9461번: 파도반 수열

#include <iostream>
using namespace std;

long long P[101] = { 0, 1, 1, 1, 2, 2, };

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	for (int i = 6; i <= 100; ++i)
	{
		P[i] = P[i - 5] + P[i - 1];
	}

	int T;
	cin >> T;
	for (int i = 0; i < T; ++i)
	{
		int N;
		cin >> N;
		cout << P[N] << '\n';
	}
}

---

 

점화식을 도출해서 푸는 다이나믹 프로그래밍 유형의 문제입니다.

 

주어진 1~10 인덱스 까지의 값을 통해서 다음과 같은 점화식을 도출할 수 있습니다.

P[1]~P[10] = { 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 }

-> 점화식: P[i] = P[i - 5] + P[i - 1]

점화식을 통해서 dp 배열에 값을 저장해 준 후 테스트 케이스 입력에 따른 인덱스의 값을 출력해주면 됩니다.

 

주의할 점은 인덱스의 크기가 일정이상 커지면 값이 int의 범위를 넘어가기 때문에

값을 저장하는 컨테이너의 자료형을 long long으로 설정해주어야 합니다.