[백준 11052 c++ V] 카드 구매하기

문제 링크

www.acmicpc.net/problem/11052

11052번: 카드 구매하기

문제 접근

// [백준 11052 c++ V] 카드 구매하기
// 문제: n 개의 카드를 구매할 때 비용의 최댓값 구하기
// 접근1: 카드 n개를 살 때의 최댓값은
//카드 n - 1개를 살 때의 최댓값 + 1번째 카드
//카드 n - 2개를 살 때의 최댓값 + 2번째 카드 ...계속
//카드 0개를 살 때의 최댓값 + n번째 카드 중 최댓값 .
// 결국 n 개를 살 때 카드의 합이 n이되는 조합들 중 최댓값을 dp 에 저장하고
// dp[0] 부터 차례로 저장해나가야 함

문제 풀이

 

주의

// 풀이: 
// 주의: n번째 dp는 카들 조합들중 최대이므로 이중 반복문이어야 함

 

개념

 

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio> // c 문법 헤더파일
#include<string> // c++ 문자열 클래스
#include<vector> // 동적배열 라이브러리
#include<stack>
#include<queue>
#include<deque>
#include<algorithm>  // sort와 unique 사용
#include<cmath> // 제곱이나 루트함수 사용
#include<cstring> // memset 함수
#include <set>
#include <map> // map구조체
#include <numeric> //accumulate(v.begin(), v.end(), 0);

// [백준 11052 c++ V] 카드 구매하기
// 문제: n 개의 카드를 구매할 때 비용의 최댓값 구하기
// 접근1: 카드 n개를 살 때의 최댓값은
//카드 n - 1개를 살 때의 최댓값 + 1번째 카드
//카드 n - 2개를 살 때의 최댓값 + 2번째 카드 ...계속
//카드 0개를 살 때의 최댓값 + n번째 카드 중 최댓값 .
// 결국 n 개를 살 때 카드의 합이 n이되는 조합들 중 최댓값을 dp 에 저장하고
// dp[0] 부터 차례로 저장해나가야 함
// 풀이: 
// 주의: n번째 dp는 카들 조합들중 최대이므로 이중 반복문이어야 함

using namespace std; // cin,cout 편하게 사용 라이브러리 
#define MAX 1001

int n;
int dp[MAX]; 
int ar[MAX];

int main()
{
	// IO 속도 향상
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);// 입출력 시간 단축
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> ar[i];
	}
	
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			dp[i] = max(dp[i], dp[i - j] + ar[j]);
		}
	}
	
	cout << dp[n];

	return 0;
}