[BOJ] 18249 : 욱제가 풀어야 하는 문제 - travelbeeee

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

---

[알고리즘풀이]

1차원 DP 문제로 점화식은 피보나치 수열과 동일하다.

#include<iostream>
#define m 1000000007;
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t, dp[191230] = { 0, 1, 2, 3, 5, };
	cin >> t;
	for (int i = 5; i < 191230; i++)
		dp[i] = (dp[i - 1] + dp[i - 2]) % m;
	while (t--) {
		int N;
		cin >> N;
		cout << dp[N] << '\n';
	}
	return 0;
}

---