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

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

9461번: 파도반 수열

---

문제 풀이

 수열을 찾는 문제이다. 

P(n)	변의 길이	계산식
P(1)	1	-
P(2)	1	-
P(3)	1	-
P(4)	2	P(1) + P(2)
P(5)	2	P(2) + P(3)
P(6)	3	P(3) + P(4)
P(7)	4	P(4) + P(5)
P(8)	5	P(5) + P(6)
P(9)	7	P(6) + P(7)

 표에서 확인 가능한 것처럼 P(n) = P(n-3) + P(n-2)이다. 자세하게 들여다보면 규칙을 쉽게 찾을 수 있다.

중요한 것은 연산을 이어나가다 보면 값이 엄청나게 커지는데 int 형으로는 잘못된 값이 나온다. 따라서 long long형으로 출력할 수 있는 값의 범위를 넓혀줘야 한다. 

느낀 점

 이 단계에서는 계속적으로 재귀 호출 시에 발생하는 시간 문제를 강조하고 있다. 이 점만 잘 숙지하면 될 것 같다.

코드

#include <iostream>

using namespace std;
long long arr[101] = { 1,1,1, };

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

int main() {
	int t, tmp;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> tmp;
		cout << p(tmp) << "\n";
	}
}