[백준/BOJ] 9461 - 파도반 수열 (c++) (DP)

1. 문제

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

---

2. 풀이

문제에서

 

P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9

 

이라고 하였다.

 

위의 수열을 보면 P(i) = P(i-2) + P(i-3)이라는 것을 알 수 있다.

 

이를 통해 코딩을 하면된다.

---

3. 소스코드

#include <iostream>

using namespace std;

int t, n, mxn = 3;
long long dp[101];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(), cout.tie();

	dp[1] = dp[2] = dp[3] = 1;

	cin >> t;
	while (t--) {
		cin >> n;
		if (mxn < n) {
			for (int i = mxn + 1; i <= n; i++) dp[i] = dp[i - 2] + dp[i - 3];
			mxn = n;
		}
		cout << dp[n] << '\n';
	}
}

---

4. 참고

 

---

질문, 고칠점 등 댓글 언제나 환영입니다.