백준 9095번 c++ 풀이

안녕하세요 오늘은 다이나믹 프로그래밍을 이용한 알고리즘 문제를 풀어보겠습니다.

 

경험상, 일반적인 다이나믹 프로그래밍 문제는 점화식이 많은 것 같습니다. 위 문제도 똑같습니다.

 

잘 생각하면 f(n-3)인 식뒤에 +3, f(n-2)인 식 뒤에 +2, f(n-1)인 식 뒤에 +1을 하면 f(n)을 만드는 식의 모든 경우의 수인것을 알 수 있습니다.

f(n)중에 마지막이 +1로 끝나는 모든 경우의 수는 f(n-1) + 1,  +2로 끝나는 모든 경우의 수는 f(n-2) + 2, +3으로 끝나는 모든 경우의 수는 f(n-3) + 3입니다

 

따라서 f(n) = f(n-1) + f(n-2) + f(n-3)임을 구했습니다.

 

그냥 재귀 호출로 하면 시간이 오래걸리므로 벡터를 하나 만들어서 호출할떄 마다 그 값을 벡터에 저장하겠습니다

코드:

#include <bits/stdc++.h>
#include <vector>

using namespace std;

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	vector<int> v(15);
	v.at(1) = 1;
	v.at(2) = 2;
	v.at(3) = 4;
	int a;
	cin>>a;
	for(int i = 0; i<a; i++){
		int b;
		cin>>b;
		if(b<=3){
			cout<<v.at(b)<<endl;
		}
		else{
			for(int j = 4; j<=b; j++){
				if(v.at(j)==0){
					v.at(j) = v.at(j-1) + v.at(j-2) + v.at(j-3);
				}
				
			}

			cout<<v.at(b)<<endl;

		}

	}
}