반응형
1. Bottom-up 방식
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;
}
반응형
'Programming > Coding Test' 카테고리의 다른 글
백준 11653 - 파이썬 처음으로 사용해보기 ! (0) | 2021.01.09 |
---|---|
9. C++ String 문법 정리 (0) | 2021.01.05 |
7. 순열과 조합 정리 (0) | 2021.01.01 |
6. DFS - 부분집합 (0) | 2020.12.31 |
5. STL 정리 (0) | 2020.12.29 |