[BOJ/DP] 백준 11052 - 카드 구매하기 / 16194 - 카드 구매하기 2 (Java)

11052 - 카드 구매하기

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

문제

카드는 카드팩의 형태로만 구매, 종류는 1개 ~ N개가 포함된 카드팩까지 총 N가지
카드의 개수가 작은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것
-> 돈을 최대한 많이 지불해서 카드 N개를 구매하려고 함
카드 i개 포함된 카드팩의 가격: $P_i$
ex. 카드팩 총 4 종류, $P_1$ = 1, $P_2$ = 5, $P_3$ = 6, $P_4$ = 7
-> 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값: 10원 (2개 들어있는 카드팩 2번)

=> 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값?
N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능
(구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 함)

입력
첫째 줄: 민규가 구매하려고 하는 카드의 개수 N (1 <= N <= 1,000)
둘째 줄: $P_i$가 $P_1$부터 $P_N$까지 순서대로 주어짐 (1 <= $P_i$ <= 10,000)
출력: 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값

---

풀이

• `cards[i]`: i장짜리 카드팩의 가격
• `dp[i]`: i장을 만들 때의 최대 가격
• `dp[i] = max(dp[i], dp[i - j] + cards[j])`
  • 나머지(`i - j`)장을 만드는 최대 가격 + j장짜리 카드팩 가격

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= i; j++) {
        dp[i] = Math.max(dp[i], dp[i - j] + cards[j]);
    }
}

---

예시

$P_1$ = 1, $P_2$ = 5, $P_3$ = 6, $P_4$ = 7

 

4장 사는 방법

• 1 + 1 + 1 + 1: 1장짜리 4개 -> 4원
• 2 + 2: 2장짜리 2개 -> 10원
• 1 + 3 -> 7원
• 4 -> 7원

=> 최댓값: 10

---

코드

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

// 카드 구매하기
public class boj_11052 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            cards[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] + cards[j]);
            }
        }

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

---

16194 - 카드 구매하기 2

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

문제

카드는 카드팩의 형태로만 구매, 종류는 1개 ~ N개가 포함된 카드팩까지 총 N가지
카드의 개수가 작은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것
-> 돈을 최소한 지불해서 카드 N개를 구매하려고 함
카드 i개 포함된 카드팩의 가격: $P_i$
ex. 카드팩 총 4 종류, $P_1$ = 1, $P_2$ = 5, $P_3$ = 6, $P_4$ = 7
-> 카드 4개를 갖기 위해 지불해야 하는 금액의 최솟값: 4원 (1개 들어있는 카드팩 4번)

=> 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최솟값?
N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능
(구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 함)

입력
첫째 줄: 민규가 구매하려고 하는 카드의 개수 N (1 <= N <= 1,000)
둘째 줄: $P_i$가 $P_1$부터 $P_N$까지 순서대로 주어짐 (1 <= $P_i$ <= 10,000)
출력
: 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최솟값

---

풀이

• `Arrays.fill(dp, Integer.MAX_VALUE)`: 큰 값으로 초기화
• `cards[i]`: i장짜리 카드팩의 가격
• `dp[i]`: i장을 만들 때의 최소 가격
• `dp[i] = max(dp[i], dp[i - j] + cards[j])`
  • 나머지(`i - j`)장을 만드는 최소 가격 + j장짜리 카드팩 가격

Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= i; j++) {
        dp[i] = Math.min(dp[i], dp[i - j] + cards[j]);
    }
}

---

예시

$P_1$ = 1, $P_2$ = 5, $P_3$ = 6, $P_4$ = 7

 

4장 사는 방법

• 1 + 1 + 1 + 1: 1장짜리 4개 -> 4원
• 2 + 2: 2장짜리 2개 -> 10원
• 1 + 3 -> 7원
• 4 -> 7원

=> 최솟값: 4

---

코드

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

// 카드 구매하기 2
public class boj_16194 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

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

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

        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j] + cards[j]);
            }
        }

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