(BOJ) 9461 파도반 수열

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

문제풀이:

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

즉, P(4)=P(2)+P(1) 이다.

소스코드:

#include <iostream> #include <vector> #include <map> #include <queue> #include <string> #include <algorithm> using namespace std; int tc, n; long long dp[101]; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); dp[1] = 1; dp[2] = 1; for (int i = 3; i <= 100; i++) { dp[i] = dp[i - 2] + dp[i - 3]; } cin >> tc; while (tc--) { cin >> n; cout << dp[n]<<'\n'; } return 0; }