백준 (BOJ) 4781 사탕가게 java greedy

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

4781번: 사탕 가게

 

이번 문제는 요약하면,

 

냅색 + 실수 처리 + rounding error 종합 세트다.

 

 

 

문제에 들어가기에 앞서, 아래의 java 코드를 보면서 값을 유추해보자.

import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        // 0.01 ~ 0.99
        for(double i = 0.01; i<100.00; i+=0.01){
            System.out.println("when i= " + i + ", rounded=" + (int)(i * 100) + ", 실제 예상되는 값= " + (int)(i * 100 + 0.5));
        }
    }
}

 

유추해보았다면, 아래는 출력에 대한 결과창이다.

 

실제로 java에서 실수 데이터를 다루다 보면 계산에 오차가 발생할 때를 자주 만날 수 있다.

 

예를 들어 i가 0.11이라고 예상되는 지점에서 예상 결과값은 11이 나와야 하는데,

 

오차 계산을 감안하지 않고 그대로 int를 통한 자동 라운딩을 해버리면 결과가 저렇게 나온다.

 

 

 

...자, 아주 간단히 말로만 풀어서 설명해 볼 것이란 말이에요.

 

실수와 실수 사이에 존재하는 실수는 무한히 많은데, 그것을 부동소수점을 통한 유한된 비트로 표현하려다보니 

 

결국 근사값에 의존해야 돼서 저런 결과가 나오는 것이란 말이에요.

 

따라서 근사값으로 표현된 것을 곧이 곧대로 사칙연산을 해서 반올림해버리면 상당히 큰 문제가 발생할 수 있다 이 말이에요. 이는 유한한 삶을 사는 우리가 유한한 자원, 그리고 유한한 비트와 유한한 시간을 가지고 무한의 세계를 표현해야 한다, 이 말이에요 자 이걸 이제 철학적으로 접근해 보면...

 

 

 

여기서 발생하는 에러를 우리는 rounding error(부동소수점 반올림 오차)라고 한다.

 

이것은 계산상의 로직 실수이기 때문에, 그 결과는 문제 없이 출력되고 그래서 결국 우리 개발자들이 에러를 잡는 데에 큰 어려움을 겪게 만들 수 있다.

 

실수를 다루게 되거든 사전에 꼭 유의하도록 하자.

 

그냥 실수를 다룬다? → rounding error 주의 이렇게 가지고 가도 될 듯하다.

 

 

 

다시 문제로 돌아와 bottom-up으로 풀어보면, 

 

0. 입력 때 실수 값을 dp 배열의 인덱스 값으로 참조할 수 없으므로 라운딩 에러에 주의해서 초기화하고 값을 받아온다.

 

1. 해당 i번째 사탕의 가격을 뽑아온다.

 

2. 한도 j 금액 만큼을 가지고 있다고 가정하고,

 

3. 그 j 금액에 사탕 가격을 뺀 남은 돈을 계산한다.

 

4. 남은 돈이 0보다 크다면 내가 가지고 있는 돈이 더 많은 것이므로,

 

5. 이전에 계산돼 왔던 dp[j] 보다 새로 계산될 dp[remainedMoney] +  cal[i]가 더 크다면, 저장해서 메모이제이션

 

6. j 한도 금액을 늘려가면서 각 사탕마다의 최적 값을 구해낸다.

 

( i가 사탕을 가리키고, j가 한도 금액 )

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int money = (int)(Double.parseDouble(st.nextToken()) * 100 + 0.5);
        StringBuilder sb = new StringBuilder();
        while (n != 0){

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

            int[] dp = new int[money+1];
            for(int i=0; i<n; ++i){
                for(int j=0; j<money+1; ++j){
                    int remainedMoney = j - cost[i];
                    if(0 <= remainedMoney){
                        dp[j] = Math.max(dp[j], dp[remainedMoney] + cal[i]);
                    }
                }
            }

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

            // 다음 테스트 케이스
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            money = (int)(Double.parseDouble(st.nextToken()) * 100 + 0.5);
        }

        System.out.print(sb);
    }
}

 

사실 소수값은 0.5로 크게 잡지 않아도 된다.

 

중요한 건, 왜 소수값을 더했는지는 위에서 rounding 결과 값을 다시 살펴보면서 생각해보자.