[BOJ] 사탕 가게 - 4781

🎨 문제

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

4781번: 사탕 가게

📘 풀이

이 문제는 DP로 풀 수 있습니다. 특히 배낭 문제를 아신다면 쉽게 풀 수 있습니다.

 

문제의 특이한 점은 사탕의 가격이 소수점 둘째자리까지 표현된 소수인 점입니다. 소수 간 연산은 오차가 발생할 수 있으므로 소수를 정수로 변환해 주었습니다. 저는 문자열에서 '.'을 지워주는 방식을 선택했습니다.

String input = "8.00";
String price = input.replace(".", "");

DP 배열은 다음과 같이 만들어 줍니다.

int[] DP = new int[사탕 종류 + 1][가지고 있는 돈 + 1]; // 최대 칼로리 저장

 

이후는 배낭문제 해법과 동일합니다. 

 

현재 사탕 번호: candy

현재 남은 금액: money

현재 사탕 가격: price

현재 사탕 칼로리: cal

 

1. 현재 위치의 기본 값은 이전 사탕에서 구한 최대 칼로리입니다. (DP[candy][money] = DP[candy - 1][money])
2. 1 ~ N번 순서로 사탕을 살지 말지 결정합니다.
3. 사탕을 샀을 경우와 안샀을 경우의 최대값을 DP[candy][money]에 저장합니다.

주의할 점은 사탕을 여러 번 살 수 있다는 점입니다. 보통 점화식을 다음과 같이 작성하는데

DP[candy][money] = max(DP[candy - 1][money],               // 현재 사탕 구매 X
                       DP[candy - 1][money - price] + cal) // 현재 사탕 구매 O

이렇게 작성하면 같은 사탕을 여러 번 살 수 없게 됩니다. 따라서 다음과 같이 작성해야 합니다.

DP[candy][money] = max(DP[candy - 1][money],               // 현재 사탕 구매 X
                       DP[candy - 1][money - price] + cal, // 현재 사탕 구매 O
                       DP[candy][money - price] + cal)     // 현재 사탕 재구매

for (int candy = 1; candy <= N; candy++) {
    String[] split = br.readLine().split(" ");
    int cal = Integer.parseInt(split[0]);
    int price = Integer.parseInt(split[1].replace(".", ""));
    for (int money = 1; money <= M; money++) {
        DP[candy][money] = DP[candy - 1][money];
        if (money < price) continue;
        DP[candy][money] = Math.max(cal + DP[candy - 1][money - price], DP[candy][money]);
        DP[candy][money] = Math.max(cal + DP[candy][money - price], DP[candy][money]);  // 같은 사탕 여러번 구매 가능
    }
}

 

📗 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N, M;
    static int[] CANDIES;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            String input = br.readLine();
            String[] split = input.split(" ");
            if (input.equals("0 0.00")) return;

            N = Integer.parseInt(split[0]);
            M = Integer.parseInt(split[1].replace(".", ""));
            int[][] DP = new int[N + 1][M + 1];
            for (int candy = 1; candy <= N; candy++) {
                split = br.readLine().split(" ");
                int cal = Integer.parseInt(split[0]);
                int price = Integer.parseInt(split[1].replace(".", ""));
                for (int money = 1; money <= M; money++) {
                    DP[candy][money] = DP[candy - 1][money];
                    if (money < price) continue;
                    DP[candy][money] = Math.max(cal + DP[candy - 1][money - price], DP[candy][money]);
                    DP[candy][money] = Math.max(cal + DP[candy][money - price], DP[candy][money]);  // 같은 사탕 여러번 구매 가능
                }
            }
            System.out.println(DP[N][M]);
        }
    }
}