백준 알고리즘 9461번: 파도반 수열 [C++]

문제 출처: www.acmicpc.net/problem/9461

9461번: 파도반 수열

1. 코드

#include <iostream>

using namespace std;

long arr[101] = { 0, 1, 1 };

long solution(int n)
{
	if (n == 0) return 0;
	else if (n == 1) return 1;
	else if (arr[n]) return arr[n];
	else return arr[n] = solution(n - 2) + solution(n - 3);
}

int main(void)
{
	int T, N;
	cin >> T;

	for (int i = 0; i < T; i++)
	{
		cin >> N;
		cout << solution(N) << "\n";
	}
	return 0;
}

(실행)

2. 풀이

풀이 방법은 피보나치 수열의 동적 계획법과 수식을 제외한 모든 것이 똑같다. 출력된 값들은 (1, 1, 1, 2, 2, 3, 4, 5, 7, 9)인데 이것 중 6번째를 기준으로 살펴보면 F(6) = F(4) + F(3) = 2 + 1 = 3이 나오니 이것을 N으로 바꾸면 F(N) = F(N - 2) + F(N - 3)이 나온다. 그리고 N - 3까지 접근을 하기 때문에 N이 2일 경우도 미리 초기화를 시켜준다.

하지만 이렇게 수식만 구하고 답을 입력하면 "틀렸습니다."가 출력이 될 것이다. 그 이유는 오버플로우가 발생하기 때문이다. 발생하는 이유는 저장해야 할 값이 너무 커지기 때문이기에 저장하는 배열과 함수의 자료형을 long으로 해주면 이 문제는 해결된다.

3. 느낀 점

이번 문제는 피보나치 수열에서 수식만 바꾸는 문제라 그렇게 어렵지 않았다.