[BaekJoon] 11052 카드 구매하기

1.  문제 링크

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

2.  문제

요약

• 카드팩의 종류는 카드 1개가 포함된 카드팩, 2개가 포함된 카드팩, ..., N개가 포함된 카드팩 이렇게 N가지가 존재합니다.
• 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿어 돈을 최대한 많이 지출하여 카드 N개를 구매하려고 합니다.
• 카드가 i개 포함된 카드팩의 가격은 Pi원입니다.
• 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값을 구하는 문제입니다.
• N개보다 많은 수의 카드를 산 후에 버리는 것은 불가능하고 구매한 카드팩들의 카드 개수의 합은 N이어야 합니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 구매하려고 하는 카드의 개수 N이 주어지고 두 번째 줄에 1보다 크거나 같고 10,000보다 작거나 같은 P1부터 Pn까지 순서대로 주어집니다.
• 출력: 첫 번째 줄에 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	static int[] prices;
	public int getMaxPrice(int num) {
		if(num == 1) {
			return prices[1];
		}
		int[] dp = new int[prices.length];
		dp[1] = prices[1];
		for(int i = 2; i <= num; i++) {
			dp[i] = prices[i];
			for(int j = 0; j <= i / 2; j++) {
				dp[i] = Math.max(dp[i], dp[i - j] + dp[j]);
			}
		}
		return dp[num];
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		prices = new int[num + 1];
		String[] input = br.readLine().split(" ");
		br.close();
		for(int i = 1; i <= num; i++) {
			prices[i] = Integer.parseInt(input[i - 1]);
		}
		Main m = new Main();
		bw.write(m.getMaxPrice(num) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DP를 이용하여 해결할 수 있습니다.
• 만약 N이 1이라면, 1장이 들어있는 카드팩을 제외하고는 구매할 수 없기 때문에 P1의 값을 출력합니다.
• 구매하려는 카드 개수에 따른 지불해야 하는 금액의 최댓값을 나타내는 1차원 배열 dp를 생성합니다.
• 우선 i개의 카드를 구매하려고 할 때, i개에 해당하는 dp 배열의 값을 Pi로 초기화시킵니다.
• 그리고 0개부터 (i / 2)개까지 각각을 j라고 한다면, j개의 카드를 샀을 때의 금액의 최댓값과 (i - j)개를 샀을 때의 금액의 최댓값을 더해나갑니다. 즉, 이전에 구했던 최대 금액을 이용하여 i개를 하나의 카드팩이 아닌 나누어 사는 방법들에서의 최대 금액을 구합니다.
• 0개부터 (i / 2)개까지 위의 방법으로 각각 최대 금액을 구해나가면서 각각을 현재 i개의 카드를 구매하려고 할 때의 최대 금액과 비교하여 더 큰 금액으로 dp[i]를 설정합니다.
• 위 방식을 바탕으로 N개까지 진행하였을 때의 dp[N]의 값이 N개의 카드를 구매하려고 할 때의 최대 금액이 됩니다.
• 위 방법을 점화식으로 나타내어 코드로 변환하면 아래와 같은 반복문이 생성됩니다.

for(int i = 2; i <= num; i++) {
	dp[i] = prices[i];
	for(int j = 0; j <= i / 2; j++) {
		dp[i] = Math.max(dp[i], dp[i - j] + dp[j]);
	}
}

• 위 점화식을 바탕으로 최대 금액을 구합니다.

1. 만약 N이 1이라면, P1의 값, 즉 위 코드에서는 prices[1]의 값을 출력합니다.
2. 구매하려는 카드 개수에 따른 지불해야 하는 금액의 최댓값을 나타내는 1차원 배열 dp를 생성하고 dp[1]의 값을 P1, 즉 prices[1]의 값으로 초기화시킵니다.
3. 2개의 카드부터 N개의 카드까지 반복문을 돌면서 해당 개수에서의 최대 금액을 구합니다.
   1. 각 개수에 대한 dp 배열의 값을 각 개수만큼 들어있는 카드팩의 금액으로 초기화합니다.
   2. 0개부터 (해당 개수 / 2)개까지 반복문을 돌면서 각 반복문에서의 개수를 j라고 한다면 dp[j] + dp[i - j]의 값을 구하고 현재 해당 개수에 대한 dp 배열의 값과 비교하여 더 큰 값을 해당 개수에 대한 dp 배열의 값으로 설정합니다.
4. 2번의 반복문을 통해 dp 배열이 채워졌을 때, dp[N]의 값이 N개의 가드를 사려고 했을 때의 최대 금액이 됩니다.