8. 동적계획법

 

 

 

1. Bottom-up 방식

www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, ...

여기서 규칙이 보이나요?

규칙은 전전 값과 전전전 값을 더한 것입니다.

이를 bottom-up 방식으로 구현해보면 아래와 같습니다.

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

int total, N;
vector<long long int> v;

int main(void) {
    
    cin >> total;
    
    v.push_back(0);
    v.push_back(1);
    v.push_back(1);
    v.push_back(1);
    
    
    for(int k=0; k<total; k++){
        cin >> N;
        
        for(int i=(int)v.size(); i<=N; i++){
            v.push_back(v[i-2] + v[i-3]);
        }
        
        printf("%lld\n", v[N]);
    }
    
    return 0;
}