계단 오르기 (feat. 백준, 2579번)

계단 오르기
https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/2579
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int N, arr[301] = { 0 }, dp[301] = { 0 };
	cin >> N;
	for (register int n = 1; n <= N; ++n)
		cin >> arr[n];
	dp[1] = arr[1];
	dp[2] = arr[1] + arr[2];
	for (register int n = 3; n <= N; ++n)
		dp[n] = max(dp[n - 2], dp[n - 3] + arr[n - 1]) + arr[n];
	cout << dp[N] << endl;
	return 0;
}
// *&)*@*

1. 3번째 계단부터 생각해주면 됩니다. 3번째 계단은 1번째 계단까지의 총합에 자신을 더하거나 0번째 계단까지의 총합에 2번째 계단의 값을 더한 경우로 2가지입니다. 즉, 두가지 중에 큰값을 취하면 되겠습니다.
2. 따라서 현재 계단까지의 총합을 Ai 라고 하고 현재 계단을 Bi 라고 한다면, Ai = max(Ai-2, Ai-3 + Bi-1) + Bi 로 수식을 구할 수 있습니다.