SMALL
안녕하세요 오늘은 다이나믹 프로그래밍을 이용한 알고리즘 문제를 풀어보겠습니다.
경험상, 일반적인 다이나믹 프로그래밍 문제는 점화식이 많은 것 같습니다. 위 문제도 똑같습니다.
잘 생각하면 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;
}
}
}
LIST
'BOJ 문제풀이' 카테고리의 다른 글
백준 1904 c++ 풀이 (0) | 2021.07.30 |
---|---|
백준 10870번 c++ 풀이 (0) | 2021.07.30 |
백준 2003번 c++ 풀이 (0) | 2021.07.29 |
백준 1463 c++ 풀이 (1) | 2021.07.28 |
백준 3273 c++ 풀이 (0) | 2021.07.26 |