백준 4781 자바 - 사탕 가게 (BOJ 4781 JAVA)

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

 

  유명한 DP 활용 문제 유형인 냅색(knapsack) 문제이다. '각 사탕의 개수는 매우 많기 때문에, 원하는 만큼 사탕을 구매할 수 있다.'라는 부분 때문에 냅색에서 난이도가 좀 낮춰지지만, 가격이 실수라서 난이도가 다시 높아진다 ㅋㅋㅋ

 

  결국 실수만 잘 처리할 수 있으면 DP를 사용해 풀 수 있다. 그래도 양심이 있는지 소수점 두번째 자리까지만 주어지고, 최대 100.00 이라서 그냥 100을 곱해서 처리하면 된다. 소수점을 처리할 방법들중 몇가지는 다음과 같다.

 

1. 주어진 실수에 100을 곱한다. -> 주의점은 입력받은 실수에 100을 곱한 후 +0.1 정도를 해줘서 소수점 오차를 없앤 후 int형으로 형변환 해야한다. 안전하게 하려면 +0.5정도 해주면 된다.

 

2. 그냥 String으로 받은 후 '.'을 제거해서 숫자로 만든다.

 

3. 내 경우엔 빠른 입력 코드를 사용해서 입력을 받았기 때문에, byte 단위로 입력받을 때 아스키코드 기준으로 '.'은 무시하도록 처리했다. (코드의 nextIntExceptDot())

 

  이 문제의 경우 일단 BruteForce로는 당연히 무리이고 (각 입력값 사탕 입력 단 하나에 대해서도 2^(m/p)번 확인해야 하므로, 대략 2^((m/각각의p)*n) 번 확인해야한다.), 그리디로 착각하기 쉬운데 예제 입력 1의 두번째 테스트 케이스만 봐도 그리디로는 무리가 있음을 알 수 있다(가격대비 칼로리정도를 기준으로 정렬하고 선택한다고 최적의 결과를 얻을 수 없음).

 

  따라서 dp[a]를 'a'로 구매 가능한 사탕의 최대 칼로리 수치로 정의해서 dp를 돌려야 한다. 예를들어 다음의 입력값을 보자. (설명의 편의를 위해 예제 입력 2번째 테스트케이스에서 소수점 부분만 없앴다. 소수점 생각 안하고 원래 정수로 들어왔다고 가정하고 설명해보겠다.)

3 8
700 7
299 3
499 5

1. 우선 dp 배열을 준비했다. dp[m+1] = dp[8+1]로 준비하면 된다.

 

 

2. 첫번째 입력값인 c=700, p=7 을 보자. p=7 이므로 dp[7] 미만은 볼 필요가 없다(idx-p<0이므로). dp 배열에서 idx가 7 이상인 지점에 dp[idx] = max(dp[idx], dp[idx-p]+c) 점화식을 적용하면 된다.

 

 

3. 두번째 입력값인 c=299, p=3을 보자. 마찬가지로 idx가 3이상에 dp 점화식을 적용하면 된다. 이번엔 표를 좀 더 세분화해서 확인해보겠다. 표에서 최종적으로 남는 값은 max값이다.

 

4. 마지막 입력값인 c=499, p=5를 보자. 마찬가지로 idx가 5 이상인 지점에 점화식을 적용하자.

 

 

5. 최종적으로 dp[m] = dp[8] = 798이 답이 된다. 추가로 m이 1~7일 때의 최대값도 위 dp를 통해 알 수 있다.

 

 

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/04700/BOJ_4781.java

import java.io.DataInputStream;
import java.io.IOException;

public class Main extends FastInput {
    private void solution() throws Exception {
        StringBuilder sb = new StringBuilder();
        while (true) {
            int n = nextInt();
            int m = nextIntExceptDot();
            if (n == 0 && m == 0) break;

            int[] dp = new int[m+1];
            for (int i = 0; i < n; i++) {
                int c = nextInt();
                int p = nextIntExceptDot();
                if (p > m) continue;

                for (int targetPrice = p; targetPrice <= m; targetPrice++) {
                    dp[targetPrice] = Math.max(dp[targetPrice], dp[targetPrice-p] + c);
                }
            }
            sb.append(dp[m]).append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    protected static int nextIntExceptDot() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            if (c == '.') continue;
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9' || c == '.');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}