[백준] 11052. 카드 구매하기

문제 링크

[백준] 11052. 카드 구매하기

풀이 과정

다이나믹 프로그래밍 문제입니다.

int[] cost = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int[] dp = new int[N];

문제의 입력은 배열 cost에 저장합니다.

dp[i] 는 카드 i장을 갖기 위해 지불해야 하는 최대 금액을 의미합니다.

dp[0] = cost[0];

한 장을 갖기 위해선 $P_{1}$원을 온전히 지불해야 하므로, dp[0] 은 cost[0] 이 됩니다.

두 개 이상의 카드를 지불하기 위한 최대값은 아래의 과정에 의해 결정됩니다. 예를 들어, dp[6]은 다음 경우들 중 하나로 확정됩니다.

• $P_6$ 원을 들여 카드팩 하나를 사버리는 경우.
• $dp[0]$ 과 $dp[5]$를 더해 카드 개수를 맞추면서 동시에 최대값이 만족하는 경우.
• $dp[1]$과 $dp[4]$를 더해 카드 개수를 맞추면서 동시에 최대값이 만족하는 경우.
• $dp[2]$와 $dp[3]$을 더해 카드 개수를 맞추면서 동시에 최대값이 만족하는 경우.

for (int i = 1; i < N; i++) {
    dp[i] = cost[i];

    for (int j = i - 1; j >= (i - 1) / 2; j--) {
        dp[i] = Math.max(dp[i], dp[j] + dp[i - j - 1]);
    }
}

그림에서 본 로직을 코드로 옮기면 위와 같습니다.

• 먼저 dp[i] 에 cost[i] 를 저장함으로써 i개가 포함된 팩을 하나 구입했을 때의 값을 최대값으로 설정해둡니다.
• j 와 i - j - 1 을 더하면 i - 1 이 되며, 이 인덱스에 해당하는 두 요소를 더하면 i개의 카드 개수를 맞출 수 있습니다. 따라서, 인덱스 j 를 낮춰가며 두 요소를 찾습니다. 이 때, j는 절반을 기준으로 대칭되므로, 절반까지만 진행합니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] cost = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] dp = new int[N];
        dp[0] = cost[0];

        for (int i = 1; i < N; i++) {
            dp[i] = cost[i];

            for (int j = i - 1; j >= (i - 1) / 2; j--) {
                dp[i] = Math.max(dp[i], dp[j] + dp[i - j - 1]);
            }
        }

        System.out.println(dp[N - 1]);
    }
}