(c++)백준 2579번: 계단 오르기

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

2579번: 계단 오르기

앞의 계단을 선택했느냐 안했느냐가 다음 계단 선택에도 영향을 끼친다. 그래서 이차원 배열을 이용하여 계단을 선택했을 때와 안 했을 때를 나누어 최댓값을 구했다.

 

※점화식※

dp[i][0] : i번째 계단을 첫 계단으로 하고, 선택하지 않을경우 점수의 최댓값

dp[i][1] : i번째 계단을 첫 계단으로 하고, 선택할 경우 점수의 최댓값

dp[n][1] = Stair[n]
dp[n - 1][0] = dp[n][1]
dp[n - 1][1] = Stair[n - 1] + dp[n][1]

<n이 3이상일 경우>

dp[n - 2][0] = dp[n - 1][1];
dp[n - 2][1] = dp[n][1] + Stair[n - 2];

 

dp[x][0] = dp[x+1][1]

dp[x][1] = max(dp[x+2][1] + Stair[x], dp[x+2][0] + Stair[x+1] + Stair[x])

 

#include <iostream>
#include <algorithm>
using namespace std;

int n;
long long dp[301][2];//0:해당 계단 선택 안 함, 1: 해당 계단 선택 함
long long Stair[301];

void DP() {
	dp[n][1] = Stair[n];
	dp[n - 1][0] = dp[n][1];
	dp[n - 1][1] = Stair[n - 1] + dp[n][1];
	if (n >= 3) {
		dp[n - 2][0] = dp[n - 1][1];
		dp[n - 2][1] = dp[n][1] + Stair[n - 2];
	}

	//뒤에서부터
	for (int i = n - 3; i >= 1; i--) {
		//현재 계단 선택 안 하면 그 다음 계단은 꼭 선택해야 함
		dp[i][0] = dp[i + 1][1];
		//현재 계단 선택하면 현재 계단 + 다다음 계단, 현재 계단 + 다음 계단 중 점수가 더 높은 걸 골라야 함
		dp[i][1] = max(dp[i + 2][1] + Stair[i], dp[i + 2][0] + Stair[i + 1] + Stair[i]);
	}

	if (dp[1][0] > dp[1][1])
		cout << dp[1][0] << endl;
	else
		cout << dp[1][1] << endl;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> Stair[i];
	}
	DP();
	return 0;
}