🖊️ 문제

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

---

🖊️ 풀이

DP를 사용해서 푸는 문제였다.

dp 잘 안해봐서 .. dp알못인 나. ..
dp라고 하면.. 현재까지의 최대값을 별도의 자료구조에 저장해놓고 연산 횟수를 줄여야겠지

이 문제에서 어떤 정보를 저장하면 좋을까? 생각해보면
각 계단 별로, 현재까지의 점수 합의 최댓값을 저장해놓으면 되겠다.

무턱대고 식부터 세우면 어려우니까
생각을 해보자.

dp[i] : i번째 계단까지의 점수 합의 최댓값

dp[0] = arr[0]
dp[1] = arr[1]과 arr[0] + arr[1] 중 더 큰 값
// -> 한 칸 오르거나, 두 칸 오르거니
dp[2] = arr[0] + arr[2] or arr[1] + arr[2]
// -> 연속 세 칸은 불가능하므로, 두 칸 전에서 오르는 경우([0]+[1]) or 한 칸 전에서 오르는 경우([1]+[2])
dp[3] = dp[1] + arr[3] or dp[0] + arr[2] + arr[3]
// -> 두 칸 전에서 오르는 경우 (두 칸 전까지의 최댓값 + 현재 계단) or 한 칸 전에서 오르는 경우 (직전값 + 현재값 + 세 칸 전까지의 최댓값 (두 칸 전은 방문 불가))

...

이렇게 하다 보면
식을 세울 수 있음

dp[i] = max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i]);

이렇게 하면 된다.

식을 세우는게 좀 복잡하다!
식만 세울줄 알면 되는 문제,,

실버3 인데
난 실딱이가 맞는 것 같다 ...

#include <iostream>
using namespace std;

int arr[300];
int dp[300];

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	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(dp[i - 2] + arr[i], dp[i - 3] + arr[i-1] + arr[i]);
	}
	cout << dp[n - 1] << '\n';
}