[백준] 단계별로 풀어보기 > 동적 계획법 1 (c++)

문제 1. 피보나치 함수

• 피보나치 f(n) 이 몇개의 f(0)과 f(1)로 이루어 져 있는지 출력하는 문제
• 점화식(?) { f(i).first, f(i).second } = { f(i-1).first+f(i-2).first, f(i-1).second+f(i-2).second } 을 찾음

#include<iostream>
#include<vector>
#include<utility>

using namespace std;

int main() {
	int test_case;
	cin >> test_case;
	
	vector<pair<int, int>> f;

	f.push_back({ 1, 0 });
	f.push_back({ 0, 1 });

	for (int i = 2; i <= 40; i++) {
		f.push_back({f.at(i-1).first + f.at(i-2).first, f.at(i-1).second + f.at(i-2).second});
	}

	int* n = new int[test_case];
	for (int i = 0; i < test_case; i++) {
		cin >> n[i];
		cout << f.at(n[i]).first << " " << f.at(n[i]).second << "\n";
	}
    
    return 0;
}

 

문제 2. 신나는 함수 실행

 

문제 3. 01타일

 

문제 4. 파도반 수열

 

문제 5. RGB 거리

 

문제 6. 정수 삼각형

 

문제 7. 계단 오르기

 

문제 8. 1로 만들기

 

문제 9. 쉬운 계단 수

 

문제 10. 포도주 시식

 

문제 11. 가장 긴 증가하는 부분 수열

 

문제 12. 가장 긴 바이토닉 부분 수열

 

문제 13. 전깃줄

 

문제 14. LCS

 

문제 15. 연속합

 

문제 16. 평범한 배낭

 

결과