[백준] 1, 2, 3 더하기

오랜만에 알고리즘 문제를 다시 꾸준히 풀어보겠다는 다짐에 백준에 들어가봤다.

Dynamic프로그래밍 문제중에 고르다가 처음에는 계단 오르기라는 문제를 풀어보려 했는데, 생각할수록 풀이가 너무 복잡해져서 포기하고 더 만만해 보이는 문제를 찾다가 풀게 됐다.

Dynamic Programing의 가장 기본 예시중 하나인 피보나치수를 이용하는 문제였다. 그럼에도 이 방법을 떠올리는데 꽤 애를 먹었다. 알고리즘 문제를 꾸준히 풀어서 뇌를 유연하게 만들어 놓을 필요가 있음을 느꼈다.

초기에 1,2,3 각각을 만들 수 있는 방법의 수를 먼저 구해서 배열에 저장하고 이를 이용하여
f(n) = f(n-1) + f(n-2) + f(n-3) 을 11까지 모두 계산해놓고, 입력되는 값에 따라 출력하도록 코드를 작성했다.

#include<iostream>
#include<vector>
using namespace std;

int main(){
int t, n;
cin>>t;

int f[12];
f[1]=1;
f[2]=2;
f[3]=4;

for(int i=4; i<=11; i++){
    f[i] = f[i-1]+f[i-2]+f[i-3];
}

vector<int> nums;
for(int i=0; i<t; i++){
    cin>>n;
    nums.push_back(n);
}    
for(int i=0; i<t; i++){
    cout<<f[nums[i]]<<endl;
}
}