백준 9461 풀이

링크텍스트

한 동안 dp 문제만 풀어서 그런지 쉽게 감을 잡을 수 있었다. 여태 해온 방식대로 F(1)부터 하나씩 증가시키며 규칙을 찾으려고 했고 결과

F(n) = F(n-2)+F(n-3)

위와 같은 점화식을 찾았다. 점화식만 찾았다면 이후는 간단하다. 끝

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <utility>
using namespace std;

int n;
int m;
long long arr[1001];

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

	int answer = 0;

	cin >> n;

	int* cases = new int[n];

	for (int i = 0; i < n; i++) {
		cin >> cases[i];
	}

	arr[1] = 1;
	arr[2] = 1;
	arr[3] = 1;
	arr[4] = 2;

	for (int i = 5; i <= 100; i++) {
		arr[i] = arr[i - 2] + arr[i - 3];
	}
	
	for (int i = 0; i < n; i++) {
		int num = cases[i];
		cout << arr[num] << '\n';
	}

	return 0;
}```