BOJ (C/C++) 11052번: 카드 구매하기

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

11052번: 카드 구매하기

---

풀이

0-1배낭문제에서 팩을 중복 사용할 수 있다고 생각하고 풀었다.

 

먼저 DP[카드 팩의 개수(i)][총 개수(j)]으로 구성된 2차원 배열을 생성하고, 팩 1의 값은 팩의 가격*개수로 구했다.

팩 i의 카드 개수(i)가 총 개수(j)보다

- 많을 경우 : 팩 i-1까지 선택한 경우(DP[i-1][j])의 값이 들어갈 수 밖에 없다.

- 적을 경우 : j개 모두 팩 i-1까지 선택한 경우(DP[i-1][j])와 j-i개를 팩 i까지 선택+팩 i 선택 (DP[i][j-i]+P[i])를 비교

                     DP[i][j] = DP[i - 1][j] > DP[i][j - i] + P[i] ? DP[i - 1][j] : DP[i][j - i] + P[i]

 

위와 같이 계산한다면 예제 1의 경우 아래와 같이 나타낼 수 있다

가격(i) \카드 개수(j)	0	1	2	3	4
1 (1)	0	1	2	3	4
5 (2)	0	1	5	6	10
6 (3)	0	1	5	6	10
7 (4)	0	1	5	6	10

---

코드

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

vector <int> P;
int DP[1001][10001]; // DP[카드 개수][총 개수]

int main() {
	int N, p;

	// input
	P.push_back(0); // i번째 원소를 i개의 카드로 맞추기 위해

	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &p);
		P.push_back(p);
	}

	// 카드 1개가 들어있는 경우 먼저 계산
	for (int j = 1; j <= N; j++) DP[1][j] = P[1] * j;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {

			// 해당 팩의 카드 개수가 많을 경우 i-1번째의 값을 그대로 가져옴
			if (i > j) DP[i][j] = DP[i - 1][j];

			// 총 갯수가 j개일 때, i-1번째 카드까지 선택한 값 vs 총 j-i개일 때 i번째 카드를 선택 값+i번째 카드 값
			else DP[i][j] = DP[i - 1][j] > DP[i][j - i] + P[i] ? DP[i - 1][j] : DP[i][j - i] + P[i];
		}
	}

	printf("%d", DP[N][N]);

	return 0;
}