백준 9461 c++ 풀이

안녕하세요 오늘은 동적 계획법 문제를 풀어볼 것입니다. 

 

전략:

1. P(n)의 값을 n+1번째 원소로 하는 배열을 선언해주고, P(n) 함수를 선언해준다.

2. P(n) = P(n-2) + P(n-3)임을 이용하여 P(n)함수를 정의해준다.

 

코드:

#include <bits/stdc++.h>
using namespace std;
long long int arr[101] = {0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, };
long long int P(int n){
	if(arr[n]){
		return arr[n];
	}
	else{
		arr[n] = P(n-2) + P(n-3);
		return arr[n];
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N;
	cin>>N;
	for(int i= 0 ; i<N; ++i){
		int x;
		cin>>x;
		cout<<P(x)<<"\n";
	}
}