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

문제

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

접근

n개의 카드를 갖기 위한 지불 금액의 최댓값을 구해야한다.

처음엔 가장 비싼 카드팩을 골라 나가는 그리디를 떠올렸지만, 중간 가격의 카드팩 두 개로 최대 금액이 나오는 경우 때문에 패스.
실버1 문제에서 그런 그리디로 풀 수 있을 리가 없지...

두번째로 떠올린 건 DP.
카드 1개일 때 최댓값, 카드 2개일 때 최댓값... 카드 n개일 때 최댓값.

3개까지는 DP[1] + DP[2] || P[3]을 비교한다.
그럼 4개는? DP[1] + DP[3] || DP[2] + DP[2] || P[4]를 비교하나?
1000개는..?

필자는 여기서 시간을 단축시킬 방법을 고민했지만 없다고 판단하여 값 k를 만들 수 있는 모든 조합을 비교해주기로 했다.
DP[1] + DP[k-1] || DP[2] + DP[k-2] || ... || P[k]

위 고민에 대한 자세한 내용은 정리에 서술하겠다.

풀이

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

public class boj_11052 {
    //public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int[] arr = new int[n + 1];
        int[] dp = new int[n + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= n; i++) {
            int j = 1;
            int max = arr[i];

            while (j <= i / 2) {
                if (dp[j] + dp[i - j] > max) max = dp[j] + dp[i - j];
                j++;
            }

            dp[i] = max;
        }

        System.out.println(dp[n]);
    }
}

정리

전형적인 DP문제이다. DP가 익숙해지면 금방 풀 수 있을 것이다.

---

위에서 했던 고민은 'Input 값의 범위가 1~1000인데, 내 로직이 제한 시간 내로 작동이 될까?' 하는 고민이었다.

결과적으로 제한 시간 내에 통과할 수 있었다.
그렇다면 고민이 불필요했다는 이야기인데...
(물론 시간을 줄일 수 있는가에 대한 접근은 필요하다고 생각함)

전에도 문제 풀 때 이런 적이 있었다.
로직을 생각해놓고 이게 제한 시간 내로 작동할지 계산이 안 되어서 코드를 다 짜고 나서야 시간 초과인 걸 눈으로 직접 보고 알았다.
멍청하긴..

조만간 해당 내용에 대한 해결법을 공부해서 블로그로 정리해 보겠다.