(백준/C++) 9461_파도반 수열

백준의 9461번: 파도반 수열 문제는 점화식을 찾기 쉬운 문제에 속합니다. 이미지가 그려져 있기 때문에, 이미지 속에서 패턴을 찾기만 하면 어렵지 않게 풀 수 있습니다.

이 문제는 동적 계획법(Dynamic Programming, DP)은 큰 문제를 작은 문제들로 나누어 풀어나가고 작은 문제의 해를 저장해 다시 계산하지 않고 사용하는 방식입니다.

동적 계획법 문제에 접근하는 만큼, 최적 부분 구조와 중복된 부분 문제의 두 가지 속성에 대해서 생각해보겠습니다.

1. 최적 부분 구조: 파도반 수열에서 특정 변은 그 이전의 특정 변들에 의존하여 구해지므로, 큰 문제의 해결이 작은 문제의 해결에 의존하는 형태입니다.
2. 중복된 부분 문제: 특정 변을 계산하기 위해 이전에 계산했던 변들의 값이 반복적으로 필요합니다.

접근법

백준의 파도반 수열 문제는 그림을 보고 점화식을 찾기만 하면 되기 때문에 어렵지 않게 규칙을 찾을 수 있습니다.

다만, 점화식을 찾을 때, 첫 값부터 찾으려고 하면 어려울 수 있습니다. 두 삼각형의 합이 하나의 삼각형의 한 면이 된다는 점을 상기하면 점화식을 찾을 수 있습니다.

이 점을 생각하며 백준에서 제공하는 이미지를 보고 접근해보겠습니다.

출처: 9461번: 파도반 수열 (acmicpc.net)

1. Top-down 접근

우선 이 문제는 큰 수가 작은 수 두 개로 만들어지고 있습니다. 따라서 이 문제를 해결하기 위해 적당한 위치에서부터 Top-down적인 접근을 해보겠습니다.

(실제 문제를 풀 때에는 Tabulation (Bottom-up) 방식으로 작은 문제들의 최적 해부터 만들어 갈 겁니다.)

1) 먼저 12를 만들기 위해서는 9와 3을 조합해서 만들면 됩니다.

2) 그리고 그 9를 만들기 위해서는 7과 2를 조합해서 만들면 됩니다.

2. 점화식 찾기

이런식으로 Top-down 적인 접근을 하면 다음과 같이 모든 문제에 대한 점화식을 찾을 수 있습니다.

Top-down 으로 점화식 찾아가기

그리고, 백준의 파도반 수열 문제는 몇 개의 케이스가 나올 지 모르기 때문에 저는 모든 케이스를 한 번에 받으면서 최대 값을 저장해 값을 저장했습니다.

---

풀이

위 방법으로 일반적인 점화식을 찾으셨다면 아마 P(N) = P(N-1) + P(N-5) 와 같은 점화식을 찾았으리라 생각됩니다.

그리고 위에서 생각의 방식은 Top-down 적으로 생각해 나아갔지만, 문제를 직접 풀 때에는 Tabulation (Bottom-up) 방식으로 풀어야 합니다.

즉, 작은 수부터 만들어야 큰 수를 만들 수 있습니다.

그런데, 큰 수를 조합하려면 적어도 N-5 번째 숫자가 있어야 합니다. 즉, 조합할 수 있는 숫자가 나올 때 까지(제 경우에는 index=5까지)는 직접 초기화 해주어야 합니다.

Tabulation으로 문제 풀기

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

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

	int N, max = 0;
	cin >> N;

	vector<int> question(N);
	vector<long long> sequence;
	
	for(int i = 0; i < N; i++)
	{
		cin >> question[i];
		if (max < question[i]) max = question[i];
	}

	//초기화
	sequence.resize(max >= 6 ? max + 1 : 6);
	sequence[0] = 0;
	sequence[1] = 1;
	sequence[2] = 1;
	sequence[3] = 1;
	sequence[4] = 2;
	sequence[5] = 2;

	//점화식: P(N-1) + P(N-5) = P(N)
	for(int i = 6; i <= max; i++)
		sequence[i] = sequence[i - 1] + sequence[i - 5];

	//출력
	for (const int i : question)
		cout << sequence[i] << '\n';
}