카드 구매하기 (feat. 백준, 11052번)

카드 구매하기
https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

반응형

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

1. P1을 선택하는 경우는 P1밖에 없습니다.
2. P2를 선택하는 경우는 P1을 선택했던 결과에 + P1을 하거나 P2가 있습니다.
3. P3을 선택하는 경우는 P2를 선택했던 결과에 + P1을 하거나 P1을 선택했던 결과에 + P2를 하거나 P3이 있습니다.
4. P4를 선택하는 경우는 P3을 선택했던 결과에 + P1을 하거나 P2를 선택했던 결과에 + P2를 하거나 P1을 선택했던 결과에 + P3을 하거나 P4가 있습니다.
5. 즉, DP1 = DP0 + P1 / DP2 = DP1 + P1 or DP0 + P2 / DP3 = DP2 + P1 or DP1 + P2 or DP0 + P3 / DP4 = DP3 + P1 or DP2 + P2 or DP1 + P3 or DP0 + P4 가 있습니다. 따라서 각각의 DP들은 or에 대해 max를 취하게 되면, 1 ~ N까지 중 최대의 값이 원하는 답이 됩니다.