[백준] [C/C++] 11052번 : 카드 구매하기 (+ 16194번)

문제

입력

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 P_i가 P₁부터 P_N까지 순서대로 주어진다. (1 ≤ P_i ≤ 10,000)

출력

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

예제 입력 1

4 1 5 6 7

예제 출력 1

10

예제 입력 2

5 10 9 8 7 6

예제 출력 2

50

알고리즘 [ 접근 방법 ]

다이나믹 프로그래밍으로 풀 수 있는 문제이다. 먼저 우리가 풀어야할 문제를 식으로 나타내면 다음과 같다.

D[N] = 카드 N개를 구매하는 최대비용 i번째 카드팩은 i개의 카드를 담고 있고, 가격은 buy[i]원이다. N개의 카드를 구매할때 카드팩은 N개가 담긴 카드팩까지 존재한다.

[ 카드팩 ] + [ 카드팩 ] + [ 카드팩 ] + [ 카드팩 ] = N개 위와 같은 형태로 최대비용을 지불하는 카드팩의 형태가 존재할 때, 하나의 카드팩에는 몇개의 카드가 존재하는지는 알 수 없다.

이때 맨 마지막 카드팩에 i개의 카드가 들어있다고 가정하면 이전의 카드팩들에는 N-i개의 카드가 들어있다고 볼 수 있다.

이를 점화식으로 나타내면 다음과같다. D[N] = D[N-i] + buy[i]

이를 코드로 구현하면 된다!

풀이1

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

int D[1001]; // N개를 구매하는데 필요한 최대 비용


int main() {
	// cin의 연산시간을 scanf만큼 줄여주기 위한 코드 2줄
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int test;
	cin >> test;
	int res = 0;

	int buy[10001]; // i개를 구매하는데 필요한 값
	D[0] = 0;
	buy[0] = 0;

	for (int i = 1; i <= test; i++) {
		cin >> buy[i];
	}

	for (int i = 1; i <= test; i++) {
		for (int j = 1; j <= i; j++) {
			D[i] = max(D[i], D[i - j] + buy[j]);
		}
	}

	cout << D[test] << endl;
}

알아두기

카드 N개를 구매하는데 필요한 최대비용을 구하는 문제였는데 그렇다면 최소비용을 구하는 문제는 어떻게 풀 수 있을까?

아주간단하다. 앞선 코드에서 max부분을 min으로 바꿔주기만 하면된다!

	for (int i = 1; i <= test; i++) {
		for (int j = 1; j <= i; j++) {
			D[i] = min(D[i], D[i - j] + buy[j]);
		}
	}

그러나 이대로 코드를 실행하게 되면 결과는 항상 0이 나온다. 카드를 구매하는 비용은 0보다 크기 때문에, min의 결과는 항상 0이다. 따라서 배열의 초기값을 잘 설정해줄 필요가 있다!

	for (int i = 1; i <= test; i++) {
		cin >> buy[i];
		D[i] = 1000 * 10000;
	}

카드의 개수 N<=1,000 이고 카드팩의 가격 <=10,000이므로 위와같이 초기값을 설정한다.

또 다른 방법으로는 D[N]을 -1로 초기화 하는 방법도 있다.

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

int D[1001]; // N개를 구매하는데 필요한 최대 비용


int main() {
	// cin의 연산시간을 scanf만큼 줄여주기 위한 코드 2줄
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int test;
	cin >> test;
	int res = 0;

	int buy[10001]; // i개를 구매하는데 필요한 값
	D[0] = 0;
	buy[0] = 10000;

	for (int i = 1; i <= test; i++) {
		cin >> buy[i];
		D[i] = -1;
	}

	for (int i = 1; i <= test; i++) {
		for (int j = 1; j <= i; j++) {
			if (D[i] == -1 || D[i] > D[i - j] + buy[j])
				D[i] = D[i - j] + buy[j];
		}
	}

	cout << D[test] << endl;
}