[백준 / BOJ] 9461번: 파도반 수열

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

9461번: 파도반 수열

 

 

---

 

코드

---

#include <iostream>
using namespace std;

long long r[101];

long long p(int n) {
	if (n <= 3) return 1;
	if (n <= 5) return 2;
	if (!r[n]) r[n] = p(n - 1) + p(n - 5);
	return r[n];
}

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

	int T, n;
	cin >> T;

	while (T--) {
		cin >> n;
		cout << p(n) << '\n';
	}
	return 0;
}

 

 

 

---

 

 

P(N)을 일일히 구하다보면 규칙이 보인다.

• N=1 -> P(N) = 1
• N=2 -> P(N) = 1
• N=3 -> P(N) = 1
• N=4 -> P(N) = 2
• N=5 -> P(N) = 2
• N=6 -> P(N) = 3 =P(1) + P(5)
• N=7 -> P(N) = 4 = P(2) + P(6)
• N=8 -> P(N) = 5 = P(3) + P(7)
• N=9 -> P(N) = 7 = P(4) + P(8)
• N=10 -> P(N) = 9 = P(5) + P(9)

N이 1~5의 값을 갖는 동안은 규칙이 없지만, 6부터는 P(N) = P(N-1) + P(N-5) 의 규칙을 갖는다. 이를 시간제한과 int형 변수로 오버플로우 없이 구현할 수 있는지를 고려하여 풀면 된다. N이 80쯤 되면 int의 범위를 넘기 때문에 long long으로 구현했다.