[C++] 백준 11052번 카드 구매하기

 

1) 문제설명

백준 Online Judge 11052번 카드 구매하기

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

11052번: 카드 구매하기

 

2) 아이디어

DP문제는 1부터 차근차근 생각해야 한다.

DP [N] : 카드를 N개 갖기 위해 지불해야 하는 금액의 최대로 설정한다.

DP [1] = 카드를 1개 갖기 위해 지불해야 하는 최대 금액 = arr [1] * 1

DP [2] = 카드를 2개 갖기 위해 지불해야 하는 최대 금액 = arr [2] * 1 or arr [1] * 2 = dp[0] + arr[2] or dp[1] + arr[1]

DP [3] = (arr[3] * 1) or (arr[2] *2 + arr[1]) or (arr[1] * 3) = (dp[0] + arr[3]) or (dp[1] + arr[2]) or (dp[2] + arr[1])

DP[3] = (카드 0개의 최대 금액 + 3개) VS (카드 1개의 최대금액 + 2개) VS (카드 2개의 최대금액 + 1개)

DP [4] = (arr[4] * 1) or (arr[3] * 1 + arr[1] * 1) or (arr[2] * 2) or (arr[1] * 4)

DP[4] = (카드 0개의 최대 금액 + 4개) VS (카드 1개의 최대금액 + 3개) VS (카드 2개의 최대금액 + 2개) VS (카드 3개의 최대금액 + 1개)

DP가 증가할수록 비교할 대상이 많아지므로 for문을 2번 사용한다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
int dp[100001]; // 카드를 n개 갖기 위해 지불해야하는 금액의 최대
int arr[100001];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	
	// dp[1] = arr[1];
	// dp[2] = arr[1] * 2 or arr[2] * 1;
	// dp[3] = arr[1] * 3 or arr[2] * 1 + arr[1] * 1 or arr[3] * 3;
	// dp[4] = arr[1] * 4 or arr[2] * 2 or arr[3] * 1 + arr[1] * 1 + arr[4] * 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			dp[i] = max(dp[i], dp[i - j] + arr[j]);
			// dp[1] = dp[1], dp[0] + arr[1]
			// dp[2] = (dp[2], dp[1] + arr[1]) || (dp[2], dp[0] + arr[2])
			// dp[3] = (dp[3], dp[2] + arr[1]) || (dp[3], dp[1] + arr[2]) || (dp[3], dp[0] + arr[3])
		}
	}
	cout << dp[n] << endl;
}