[백준/DP] 11052번 카드 구매하기 (JAVA)

문제

---

풀이

처음에 문제에 접근할 때 잘못된 생각으로 접근해서 몇 분 동안 삽질을 해버렸다. dp 배열을 i번째 카드셋까지 이용했을 때 n을 만들기 위한 최대 비용으로 설정한 것이다. 이렇게 하면 앞서 계산해 놓은 값을 전혀 활용하지 못 한다.

그래서 다시 생각의 과정을 거쳐 dp를 i개의 카드를 살 때의 최대 비용을 저장하는 배열로 설정했다. 그랬더니 앞의 값들을 활용해서 현재 값을 쉽게 구할 수 있었다.

i개의 카드를 사기 위해서는

1. i개 짜리 카드뭉치를 1개 구매: dp[i] = prices[i]
2. i-1, i-2, ... i/2개를 구매하는 최대 비용에 카드 j개를 구매하는 최대 비용 추가: dp[i] = dp[j] + dp[i-j]

이렇게 크게 두 가지 경우의 수가 가능하다. 이것들 중 최댓값을 dp[i]에 저장하고, 최종적으로 dp[n]을 반환하면 정답이 된다.

이를 코드로 표현한 것은 아래와 같다.

코드

import java.io.*;

public class Main {

    private static final int MAXIMUM = 1000;

    private static int n;
    private static int[] prices = new int[MAXIMUM + 1];
    private static int[] dp = new int[MAXIMUM + 1];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        String[] line = br.readLine().split(" ");
        for (int i = 1; i <= n; i++)
            prices[i] = Integer.parseInt(line[i - 1]);

        dp();
        bw.append(String.valueOf(dp[n]));

        br.close();
        bw.close();
    }

    private static void dp() {
        for (int i = 1; i <= n; i++) {
            dp[i] = prices[i];
            for (int j = 1; j <= i / 2; j++)
                dp[i] = Math.max(dp[i], dp[j] + dp[i - j]);
        }
    }
}