[백준] 4781 사탕 가게 - Java

 

 

 

문제 출저 

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

4781번: 사탕 가게

 

 

 

문제 풀이

사탕 종류와 상근이가 가진 돈이 주어진다. 사탕은 가격과 칼로리가 있다. 상근이 가진 돈에서 가장 큰 칼로리를 구해야 한다. 사탕은 여러 번 살 수 있다. 

 

냅색 알고리즘을 적용해 풀었습니다. 단 돈이 소수점 둘째 자리로 주어집니다. dp 배열에 길이를 돈이 담당하기 위해 100을 곱해 정수로 만들었습니다. 소수에서 정수로 변환하는 과정에서 rounding error를 해결하기 위해 0.5를 더했습니다. 

 

 

 

소스 코드

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

/*
사탕 가게
https://www.acmicpc.net/problem/4781

5000 * 10000 = 500,000,000 5억
시간초 제한 3초 3억



87% 오답
rounding error(부동 소수점 반올림 오차)
Java에서 실수 데이터를 다루다 보면 계산에 오차가 발생하는 경우가 있다.
int를 통한 자동 라운딩을 하면 0.11이 11이 나와야 하지만 10이 나오는 경우이다.
실수를 다룰 때는 rounding error를 주의해야 하며 0.5를 더하는 것으로 해결할 수 있다.

0,5를 도허눈 곳운 아래 값을 반올림하는 가장 간단한 기법이기 때문입니다.
원래 수가 0.5 미만일 때 (예: 2.3) → 0.5를 더하면 2.8이 되고, 정수 변환 시 2로 반올림됩니다.
원래 수가 0.5 이상일 때 (예: 2.7) → 0.5를 더하면 3.2가 되고, 정수 변환 시 3으로 반올림됩니다.
더 정확한 방법으로는 BigDecimal을 사용하는 방법이 있습니다.
 */

public class Main {

    static int n; // 사탕 종류 수
    static int m; // 상근이가 가진 돈의 양
    static StringBuilder sb;
    static int[] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        while(true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            float tempM = Float.parseFloat(st.nextToken());

            if (n == 0 && tempM == 0.00) {
                System.out.println(sb);
                return;
            }

            m = (int) (tempM * 100 + 0.5);

            dp = new int[m+1];
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                int calorie = Integer.parseInt(st.nextToken());
                int money = (int) (Float.parseFloat(st.nextToken()) * 100.0 + 0.5);

                for (int j = 0; j <= m; j++) {
                    if (j - money >= 0) dp[j] = Math.max(dp[j], dp[j-money] + calorie);
                }
            }

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

        }


    }

}