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

 

문제 URL:

11052번: 카드 구매하기 (acmicpc.net)

11052번: 카드 구매하기

카드가 1개가 포함되어 있는 카드부터 N개가 포함되어 있는 카드까지 각각의 카드팩이 존재한다. 각 카드팩의 가격이 주어질 때, 원하는 개수의 카드팩을 사는 최대 비용을 출력하는 프로그램을 작성하자.

 

먼저 카드팩의 가격을 arr[i]에 담고

이전 카드팩의 최대 비용인 dp[i-j]에 arr에 담긴 카드팩의 가격을 하나씩 추가해서 최댓값을 구하면 된다.

ex. 카드 4개를 구매할 때 dp[3] + arr[1], dp[2] + arr[2]를 비교하여 더 큰 값을 dp[4]에 대입 

---

#include<iostream>
#include<algorithm>
using namespace std;

int n;
int arr[10001];
int dp[10001];

int main(){
	cin >>  n;
	for (int i = 1; i <= n; i++){
		cin >> arr[i];
	}

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