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

문제 링크

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

11052번: 카드 구매하기

 

카드 4개를 살 때의 최댓값은

 

1. 카드 3개를 살 때의 최댓값 + 1번째 카드

2. 카드 2개를 살 때의 최댓값 + 2번째 카드

3. 카드 1개를 살 때의 최댓값 + 3번째 카드

4. 카드 0개를 살 때의 최댓값 + 4번째 카드

 

위 4가지 방법 중 최댓값을 구하면 됩니다.

 

따라서 카드 n개를 살 때의 최댓값은

카드 n-1개를 살 때의 최댓값 + 1번째 카드

카드 n-2개를 살 때의 최댓값 + 2번째 카드

.

.

카드 0개를 살 때의 최댓값 + n번째 카드 중 최댓값 구하면됩니다.

 

 

구현 코드

 

	#include <iostream>
	#include <algorithm>
	using namespace std;
	const int MAX = 1001;
	int dp[MAX];
	int cards[MAX];
	int main(){
	int n;
	cin >> n;
	for(int i=1;i<=n;i++)
	cin >> cards[i];
	for(int i=1;i<=n;i++)
	for(int j=1;j<=i;j++)
	dp[i] = max(dp[i], dp[i-j] + cards[j]);
	cout << dp[n] << endl;
	return 0;
	}

view raw 11052.cpp hosted with ❤ by GitHub