[백준/CPP] 계단 오르기 - 2579

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

2579번: 계단 오르기

 

다이나믹 프로그래밍 문제

문제의 조건을 만족하면서 4번째 계단을 오르기 위해서는 빨간색 체크 표시 순서로 이동하거나 파란색 동그라미 순서로 이동하는 방법 밖에 없다.

 

첫번째 계단의 최댓값은 첫 계단을 밟았을 때가 되고,

두번째 계단의 최댓값은 첫 계단과 두 번째 계단의 합이 된다.

세번째 계단의 최댓값은 1번 계단 + 3번 계단 or 2번 계단 + 3번 계단 중 큰 값이다.

dp[0] = vc[0];
dp[1] = vc[0] + vc[1];
dp[2] = max(vc[0] + vc[2], vc[1] + vc[2]);

이렇게 DP를 위한 초기값을 세팅해주고 4번째 계단을 밟을 경우 최댓값을 구하는 식을 세우면

 

빨간 체크 방식인 (i번째 계단 점수) + (i - 1번째 계단 점수) + (i - 2번째 계단의 최대 누적값) 과

파란 원 방식인 (i번째 계단 점수) + (i - 2번째 계단의 최대 누적값) 중 큰 값을 골라서 현재 계단의 최대 누적값으로 갱신해주면 된다.

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int stairs; cin >> stairs;
	int* dp = new int[stairs + 1];
	
	vector <int> vc;

	for (int i = 0; i < stairs; i++) {
		int c; cin >> c;
		vc.push_back(c);
	}

	dp[0] = vc[0];
	dp[1] = vc[0] + vc[1];
	dp[2] = max(vc[0] + vc[2], vc[1] + vc[2]);

	for (int i = 3; i < stairs; i++) {
		dp[i] = max(vc[i] + vc[i - 1] + dp[i - 3], vc[i] + dp[i - 2]);
	}

	cout << dp[stairs - 1];

}