[백준] 2579번 : 계단 오르기

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

2579번: 계단 오르기

---

<C++>

#include <bits/stdc++.h>
using namespace std;
int arr[301];
int dp[301];
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	dp[0] = arr[0];
	dp[1] = max(arr[0] + arr[1], arr[1]);
	dp[2] = max(arr[0] + arr[2], arr[1] + arr[2]);
	for (int i = 3; i < n; i++)
	{
		dp[i] = max(arr[i] + dp[i - 2], arr[i] + arr[i - 1] + dp[i - 3]);
	}
	cout << dp[n - 1] << endl;
}

 

> 개인적으로 의문을 가졌던 점은, dp[i] = max(arr[i] + dp[i - 2], arr[i] + arr[i - 1] + dp[i - 3]); 에서, 

'arr[i-1]+dp[i-3] 을 dp[i-1]로 대신하면 안되는 이유' 였습니다. 그 이유는 간단합니다.

만약 arr[i-1]+dp[i-3]을 dp[i-1]로 고치면, 이는 다시 말해, arr[i] + dp[i - 1]는

도착지점의 계단의 점수 + 도착점 바로 직전 계단까지의 점수 최대값 이라고 이해할 수 있으므로, 이렇게 해도 맞는 답이 아닐까 라고 생각할 수 있지만, 만약 i-1칸의 계단을 오기 위해 i-3의 계단이 아닌 i-2의 계단을 밟았다고 가정을 한다면, i-2, i-1,i의 계단을 밟은것이 되기 때문에, 세 계단을 연속해서 밟게 되는 경우가 생기게 됩니다. 물론 i-1칸의 계단을 오기 직전에 i-3을 밟은 경우도 존재할 수 있습니다. 이 경우에는 문제에 주어진 조건에 위배되지 않습니다. 하지만, 위에서 언급한 것 처럼 i-2계단을 밟고 i-1계단을 밟는 경우에는 문제가 됩니다.