[BOJ] 4781. 사탕 가게

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

4781번: 사탕 가게

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

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

        int n, m, c, p;
        int[] cal, price;
        int[][] dp;
        StringTokenizer st;
        StringBuilder builder = new StringBuilder();

        while (true) {
            String s = br.readLine();

            if (s.equals("0 0.00")) {
                break;
            }

            st = new StringTokenizer(s);
            n = Integer.parseInt(st.nextToken());
            m = (int) (Double.parseDouble(st.nextToken()) * 100 + 0.5);
            cal = new int[n + 1];
            price = new int[n + 1];

            for (int i = 1; i <= n; ++i) {
                st = new StringTokenizer(br.readLine());
                c = Integer.parseInt(st.nextToken());
                p = (int) (Double.parseDouble(st.nextToken()) * 100 + 0.5);
                cal[i] = c;
                price[i] = p;
            }

            dp = new int[n + 1][m + 1];
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= m; ++j) {
                    if (j - price[i] >= 0) {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - price[i]] + cal[i]);
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }

            builder.append(dp[n][m]).append("\n");
        }

        bw.write(builder.toString());

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

• 다이내믹 프로그래밍 문제
• DP 알고리즘 중 유명한 0/1 배낭 문제이다.
• 주의할 점은 double형에 100을 곱해 int형으로 변환할 때 0.5를 더해줘야 한다.
• 소수점은 2의 거듭제곱이 아닌 이상 오차가 존재할 수밖에 없기 때문에 0.5를 더해줘야 손실을 방지할 수 있다.