[백준] 동적 프로그래밍 - 11052번 카드 구매하기 (Java)

문제링크

11052번: 카드 구매하기

접근한 방법

• 동적 프로그래밍

---

풀이방법

아래 문제를 응용하여 풀이방법을 생각해보았다.

출처 : 2020/11/10 - [알고리즘/이것이 코딩테스트다] - Chapter 08 동적 프로그래밍 - 효율적인 화폐 구성 (java)

 

• $p_{0,i}$ : 카드 i개가 포함된 카드팩의 단위
• $p_{1,i}$ : 카드 i개가 포함된 카드팩의 가격
  
  
• $a_{j}$ : 카드 j개를 갖기 위해 지불할 수 있는 최대 금액
• $a_{j-p_{0,i}}$ : 카드팩에 단위를 $p_{0,i}$라고 했을 때, 카드의 개수 (j-$p_{0,i}$)를 갖기 위해 지불할 수 있는 최대금액
               (j-$p_{0,i}$ : 카드의 개수 j에서 카드팩의 카드 단위 $p_{0,i}$를 뺀 금액)

 

이 문제를 점화식으로 표현해보면 아래와 같다.

$a_{j-p_{0,i}}$를 만드는 방법이 존재 O	$a_{j} = max(a_{j}, a_{j-p_{0,i}}+1)$	카드 단위 작은 것부터 계산했을 때 얻어진 $a_{j}$와 (j-$p_{0,i}$)의 카드 금액에 현재 카드팩의 금액을 더한 것 중 최대
$a_{j-p_{0,i}}$를 만드는 방법이 존재 X	$a_{j} = 0$

예시)

n = 4

카드팩의 카드 개수 단위 $p_{0,i}$ = {1,2,3,4}

카드팩의 금액 $p_{1,i}$ = {1,5,6,7}

* 반복문의 처음 시작은 1부터 시작

 

step 1 카드 단위 : 1, 카드팩의 금액 : 1

 

j	$a_{j}$	설명
1	1	max(0, $a_{1} = a_{0} + 1$) = max(0, 1) = 1
2	2	max(0, $a_{2} = a_{1} + 1 $) = max(0, 2) = 2
3	3	max(0, $a_{3} = a_{2} + 1 $) = max(0, 3) = 3
4	4	max(0 , $a_{4} = a_{3} + 1 $) = max(0, 4) = 2

 

step 2 카드 단위 : 2, 카드팩의 금액 : 5

j	$a_{j}$	설명
1	1	카드 단위가 2부터 시작하여 검사하지 않으므로, 1로 고정되어있음
2	5	max(0, $a_{2} = a_{0} + 5 $) = max(2, 5) = 5
3	6	max(0, $a_{3} = a_{1} + 5 $) = max(0, 6) = 6
4	10	max(0, $a_{4} = a_{2} + 5 $) = max(0, 10) = 10

 

step 3 카드 단위 : 3, 카드팩의 금액 : 6

j	$a_{j}$	설명
1	1	카드 단위가 3부터 시작하여 검사하지 않으므로, 1로 고정되어있음
2	5	카드 단위가 3부터 시작하여 검사하지 않으므로, 5로 고정되어있음
3	6	max(0, $a_{3} = a_{0} + 6 $) = max(2, 6) = 6
4	10	max(0, $a_{4} = a_{1} + 6 $) = max(10, 7) = 10

 

step 4 카드 단위 : 4, 카드팩의 금액 : 7

j	$a_{j}$	설명
1	1	카드 단위가 3부터 시작하여 검사하지 않으므로, 1로 고정되어있음
2	5	카드 단위가 3부터 시작하여 검사하지 않으므로, 5로 고정되어있음
3	6	카드 단위가 3부터 시작하여 검사하지 않으므로, 6로 고정되어있음
4	10	max(0, $a_{4} = a_{0} + 7 $) = max(10, 7) = 10

 

소스코드 작성 방법

• a배열의 크기를 n+1로 지정
• 이중 반복문을 사용
  - i를 1부터 카드개수의 최종합 n이 되기까지 범위로 지정
  - j=카드팩의 단위(p[0][i])부터 카드개수의 최종합 n이 되기까지 범위로 지정
• a[j - p[0][i]] + p[1][i] : (j-카드팩의 단위(p[0][i])의 카드 금액에 현재 카드팩의 금액(p[1][i])을 더함
• Math.max를 이용해서 이전까지 구해진 a[j]와 a[j - p[0][i]] + p[1][i] 를 비교하여 a[j] 저장
• 최종값 a[n]이 구하고자하는 최댓값

 

소스코드

package baekjoon.dp;
import java.io.*;
import java.util.StringTokenizer;

public class Q_11052_PurchaseCard {
    public static int solution(int n, int[][] p) {
        int[] a = new int[n+1];

        for (int i = 1; i <= n; i++) {
            for(int j=p[0][i] ; j<=n ; j++) {
                a[j] = Math.max(a[j], a[j - p[0][i]] + p[1][i]);
            }
        }

        return a[n];
    }

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

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[][] p = new int[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            p[0][i] = i;
            p[1][i] = Integer.parseInt(st.nextToken());
        }

        bw.write(solution(n,p)+"\n");

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