[자바로 푸는 백준] 11052번 카드 구매하기

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

11052번: 카드 구매하기

✅ 실버 Ⅰ

 

🔶 풀이

N개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값을 구하시오.

 

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

예제 2번으로 규칙을 찾아보겠다.

 

카드팩은 총 5개이고, 카드 5개를 구매하기 위해 지불해야 하는 최대 금액을 찾으면 된다.

P1 = 10, P2 = 9, P3 = 8, P4 = 7, P5 = 6

card[1] = 10, card[2] = 9, card[3] = 8, card[4] = 7, card[5] = 6

 

dp배열을 생성 후에 카드 1개를 구매했을때부터 순차적으로 알아보겠다.

 

dp[1] - 1개 구매

1개의 카드팩(P1)만 구매할 수 있다.

dp[1] = card[1] = 10

 

dp[2] - 2개 구매

1. 카드를 하나도 구매하지 않은 경우에는 2개의 카드팩(P2)을 구매할 수 있다.

dp[2] = card[2] = 9

 

2. 카드를 이미 한 개 구매한 경우에는 1개의 카드팩(P1)을 구매할 수 있다.

dp[2] = dp[1] + card[1] = 20 (10 + 10)

 

dp[3] - 3개 구매

1. 카드를 하나도 구매하지 않은 경우에는 3개의 카드팩(P3)을 구매할 수 있다.

dp[3] = card[3] = 8

 

2. 카드를 이미 한 개 구매한 경우에는 2개의 카드팩(P2)을 구매할 수 있다.

dp[3] = dp[1] + card[2] = 19 (10 + 9)

 

3. 카드를 이미 두 개 구매한 경우에는 1개의 카드팩(P1)을 구매할 수 있다.

dp[3] = dp[2] + card[1] = 30 (20 + 10)

 

dp[4] - 4개 구매

1. 카드를 하나도 구매하지 않은 경우에는 4개의 카드팩(P4)을 구매할 수 있다.

dp[4] = card[4] = 7

 

2. 카드를 이미 한 개 구매한 경우에는 3개의 카드팩(P3)을 구매할 수 있다.

dp[4] = dp[1] + card[3] = 17 (10 + 7)

 

3. 카드를 이미 두 개 구매한 경우에는 2개의 카드팩(P2)을 구매할 수 있다.

dp[4] = dp[2] + card[2] = 28 (20 + 8)

 

·

·

(생략)

·

·

 

dp[5] - 5개 구매

1. 카드를 하나도 구매하지 않은 경우에는 5개의 카드팩(P5)을 구매할 수 있다.

dp[5] = card[5] = 6

 

·

·

(생략)

·

·

 

5. 카드를 이미 4개 구매한 경우에는 1개의 카드팩(P1)을 구매할 수 있다.

dp[5] = dp[4] + card[1] = 50 (40 + 10)

 

 

규칙성이 보인다.

dp[1] = 1번, dp[2] = 2번, dp[3] = 3번, dp[4] = 4번, dp[5]  = 5번의 연산이 진행됐다.

 

i = 5 라고 가정해 보면

dp[i] = dp[i-5] + card[5]

dp[i] = dp[i-4] + card[4]

dp[i] = dp[i-3] + card[3]

dp[i] = dp[i-2] + card[2]

dp[i] = dp[i-1] + card[1]

 

card에 들어간 인덱스를 j라고 했을 때,

dp[i] = Math.max(dp[i], dp[i-j] + card[j]) 의 점화식이 나온다.

 

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine()); // 구매해야할 카드 개수
        int[] card = new int[N+1]; // 카드 가격
        int[] dp = new int[N+1];   // dp
        
        st = new StringTokenizer(br.readLine());
        for (int i=1; i<=N; i++) {
            card[i] = Integer.parseInt(st.nextToken());
        }
        
        for (int i=1; i<=N; i++) {
            for (int j=1; j<=i; j++) {
                dp[i] = Math.max(dp[i], dp[i-j] + card[j]);
            }
        }
        
        System.out.println(dp[N]);
    }
}