[백준 11052] 카드 구매하기 (Java)

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

11052번: 카드 구매하기

접근 방식

이전에 풀어봤던 문제(아마도 백준 2293 동전 문제인 듯하다)와 유사한 부분이 있어서

크게 어렵지 않게 풀 수 있었던 DP문제였다.

 

문제에서 주어진 예시를 가지고 설명을 하고자 한다.

 

민규가 구매하려고 하는 카드의 개수 N = 4

P1 = 1, P2 = 5, P3 = 6, P4 = 7

 

n개의 카드를 갖기 위해 지불하는 금액의 최댓값을 dp[n]이라고 하자.

 

만약 민규가 카드 1개를 갖는다고 한다면

그 경우는 P1을 고르는 경우 하나이다.

따라서 dp[1] = p1이다.

 

만약 민규가 카드 2개를 갖는다고 한다면

2개가 들어있는 카드팩 1개를 사던가, 1개짜리 카드팩 2개를 사는 경우이다.

지불 금액의 최댓값을 구해야하기 때문에

dp[2] = MAX(P[2], dp[1] + dp[1])이다.

 

만약 민규가 카드 3개를 갖는다고 한다면

3개가 들어있는 카드팩을 1개 사던가, 2개짜리 카드팩과 1개짜리 카드팩을 각각 하나씩 사던가, 아니면 1개짜리 카드팩 3개를 사는 경우이다.

따라서 dp[3] = MAX(P[3], dp[2] + dp[1], dp[1] *3)

 

여기서 구체적으로 비교를 해보자.

dp[1] * 3 은 dp[1] * 2 + dp[1]과 같다.

dp[2] + dp[1] 과 dp[1] * 2 + dp[1]을 비교할 때,

사실상 dp[2]와 dp[1] * 2의 비교가 된다.

 

앞서 dp[2]의 값을 넣을 때 P[2]와 dp[1] * 2 중 큰 값을 dp[2]에 넣었다.

그러므로 당연히 dp[2] >= dp[1] * 2 이기 때문에

dp[3]의 값을 찾을 때 dp[1] * 3은 할 필요가 없다.

결국, dp[3] = MAX(P[3], dp[2] + dp[1]) 이다.

 

마지막으로 민규가 카드 4개를 갖는다고 한다면

dp[4] = MAX(P[4], dp[3] + dp[1], dp[2] + dp[2]) 이다.

 

따라서 다음과 같은 점화식이 도출된다.

dp[n] = MAX(P[n], dp[n - 1] + dp[1], dp[n - 2] + dp[2] ..., dp[1] + dp[n - 1])

여기서 dp[n-1] + dp[1] == dp[1] + dp[n-1]이기 때문에

 

정확한 점화식은

dp[n] = MAX(P[n], dp[n - 1] + dp[1], dp[n - 2] + dp[2] ..., dp[n - n/2] + dp[n/2])

 

소스 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int[] P = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            P[i] = scanner.nextInt();
        }

        int[] dp = new int[N + 1];

        dp[1] = P[1];

        for (int i = 2; i <= N; i++) {
            dp[i] = P[i];

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

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