C++ 알고리즘 - 백준 2579 계단 오르기 (다이나믹 프로그래밍)

https://www.acmicpc.net/problem/2579

 

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

int main(void) {
	/************** C++ Init **************/
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	/************** C++ Init **************/


	int input1, input2;
	int score = 0;
	vector<int> v;
	vector<int> v2;
	cin >> input1;

	for (int i = 0; i < input1; i++) {
		cin >> input2;
		v.push_back(input2);
	}

	v2.push_back(v[0]);
	v2.push_back(v[0] + v[1]);
	v2.push_back(max(v[0] + v[2], v[1] + v[2]));

	for (int i = 3; i < v.size(); i++) {
		v2.push_back(max(v2[i - 2] + v[i], v2[i - 3] + v[i - 1] + v[i]));
	}

	cout << v2[input1 - 1];
}

 

점화식

계단 1개 : 1번

계단 2개 : 1번 + 2번

계단 3개

1번 + 3번

&

2번 + 3번 중 최대값

 

계단 4개부터

마지막 계단 - 2칸의 최고값 + 지금 계단 값

&

마지막 계단 - 3칸의 최고값 + 지금 계단 - 1칸의 값 + 지금 계단 값 중 최대값