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

 

---

 

• 코드

정답 코드 :

민규가 구매하려고 하는 카드의 개수 N = 4, P1 = 1, P2 = 5, P3 = 6, P4 = 7

 

n개의 카드를 갖기 위해 지불하는 금액의 최댓값을 dp[n]이라고 할 때, 민규가 카드 1개를 갖는다고 한다면 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[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[n - n/2] + dp[n/2])

 

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] array = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }

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

        dp[1] = array[1];

        for(int i = 2; i <= N; i++) {
            dp[i] = array[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]);
    }
}