[동적계획법, 난이도 중] 백준 11052번 카드 구매하기

카드팩을 고를 때 중복을 허용한다는 점에서 조금 까다로울 수 있다.

그러나 이 문제도 점화식 한줄로 풀 수 있다.

 

카드를 가질 수 있는 경우는 무수히 많기 때문에 동적계획법으로 제한 장 수별로 최댓값을 구해놓아야 한다.

카드를 n개 가져야 할 경우 카드n개팩 그 자체가 가장 비쌀 수도 있고, 카드 n-i개 팩을 사는 최대비용의 경우에 i개 팩을 추가로 샀을 때가 가장 비쌀 수도 있다. 이렇게 동적 계획법으로 접근하면 n개의 경우만을 계산하여 최댓값을 구할 수 있다.

본인이 가져온 예제는 입력 예제4 이다.

처음 한 개 팩을 사는 비용은 5이다.

카드 2장을 사는 경우의 수는 (카드 2장짜리 팩값, 카드 1장을 사는 최대 비용 + 카드 1장짜리 팩값)

이 둘이고, 모두 비용은 10이라 표시는 안난다.

카드 3장을 사는 경우의 수는 (카드 3장짜리 팩값, 카드 2장을 사는 최대 비용 + 카드 1장짜리 팩값, 카드 1장을 사는 최대 비용 + 카드 2장짜리 팩값) 3가지고 각각 비용은 11, 15, 15 이므로 최댓값은 15이다.

이런 방법으로 N개짜리 팩까지 확인하면 된다.

 

#include <iostream>
#include <vector> 
#include <algorithm>
#include <string> 
#include <math.h> 
#include <stdio.h>

using namespace std;
int p[1001];
int maxp[10001];
int max(int a, int b) {
	if (a > b) return a;
	else return b;
}
int main() {
	cin.tie(NULL);
	int a;
	cin >> a;
	for (int i = 1;i < a + 1;i++) {
		cin >> p[i];
	}
	for (int i = 1;i < a + 1;i++) {
		for (int j = 1;j < i + 1;j++) {
			maxp[i] = max(maxp[i], maxp[i - j] + p[j]);
		}
	}
	cout << maxp[a];
}