풀이 아이디어

키워드 3가지로 정리하면 "정수변환, DP, 배낭문제"이다.
소수 둘째자리까지 있는 가격을 $\times100$을 해서 정수로 변환하고
최대 칼로리를 저장할 배열 DP에 0~$M\times100$ 범위의 인덱스로 표현해
그 가격까지 만들 수 있는 최대 칼로리를 DP[index]에 저장한다.
마지막에 DP[$M\times100$]일 때의 칼로리를 출력한다.

트러블 슈팅

1) 가격이 소수점으로 주어지는데 어떻게 해결하지?

DP를 써서 동전계산하듯이 계산하려고 보니 가격이 양의 소수인 게 문제가 되었다.
그래서 정수로 변환하기 위해 처리하면 편할 것 같았다.
문제를 보면 돈의 양 m이 (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00)범위로 주어지므로
100을 곱해 $1 ≤ m*100 ≤ 100$으로 처리해도 괜찮겠다는 판단이 들었다.

2) float을 int로 바꾸기

가격 계산을 용이하게 하기 위해 실수를 정수로 바꿔서 해결하려고 했는데
그 과정에서 문제가 생겼다. float을 int로 계산하는 과정에서 문제가 발생한 것.

부동소수점 오차

float같은 소수에서 int형의 정수로 바꾸는 과정에서 마주하는 문제를
"부동소수점 오차(Floating Point Error)" 또는
"부동소수점 반올림 오류(Floating Point Rounding Error)"라고 한다.

컴퓨터가 실수를 표현하는 방식에서 오차가 발생하고 특히 실수를 정수로 변환할 때 원하지 않는 값으로 변환될 수 있다.
예를 들어 8.00에 100을 곱하면 우리는 당연히 800이 될꺼라 생각하지만
실제로 계산해보면 8.00을 담는 과정에서 7.9999999....8로 표현될 수 있고
이 값을 int로 변환하면 799가 될 수 있다.

왜 부동소수점 오차가 발생할까?

8.00이라는 실수를 담을 때 컴퓨터는 이진법으로 수를 담게 되는데
10진법 수를 2진법으로 담는 과정에서 오차가 발생한다.

분수 5/3을 실수로 표현할 때 소수 10째자리까지 표현한다고 하면
1.6666666667로 표현되는데 정확하게 표현하지 못하고 오차가 발생하듯이

실수를 비트에 표현할 때 오차가 발생한다.
왜냐하면 비트에 담을 수 있는 자릿수가 한계가 있기 때문이다.
예를 들어 float은 2-127~2-128까지 표현할 수 있는데
이 범위를 넘어가는 소수점을 표현하는 과정에서 오류가 발생한다.

어떻게 해결할까?

크게 2가지 방법이 있었다.

• 1. 특정 오차 범위까지는 동일한 값으로 간주하기
     float->double로 바꾸고 +0.5를 해주기
     정수로 변환해서 사용하는 경우 일정 근사값까지는 같은 수로 쳐주기 위해서
     $99.5≤100≤100.5$는 같은 100이라고 간주하는 것이다.
     이때 변환한 단위는 1이므로 반올림이 되는 절반인 0.5를 더해주면서
     double->int로 바뀌는 오차를 줄이는 것이다.
• 2. BigDecima를 사용하기
     이 방법의 경우 정수부분과 소수부분 모두 10진법으로 표현해서 문제를 해결한다.
     다만 단점으로는 그냥 float, double로 표현할 때보다 메모리를 많이 사용한다는 단점이 있다.

코딩 테스트의 경우 메모리 제한도 엄격하고 기본 라이브러리를 제외한 외부 라이브러리 사용이 불가능한 경우가 있기 때문에 1번 방법을 사용해서 풀기로 했다.

풀이 코드

import java.util.*;
import java.io.*;


public class _4781 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // n: 가게에 있는 사탕 종류의 수
        // m: 가지고 있는 돈
        int n = Integer.parseInt(st.nextToken());
        int m = (int)(Double.parseDouble(st.nextToken())*100+0.5);

        // 돈의 양이 소수점 둘째자리까지 주어지는데 어떻게 처리하지?
        // 그냥 100 곱해서 정수로 만들어버리자.

        while(n!=0 || m!=0){
            int[] dp = new int[m + 1];
            for(int i = 0; i < n; i++){
                st = new StringTokenizer(br.readLine());
                // c: 칼로리
                // p: 가격
                int c = Integer.parseInt(st.nextToken());
                int p = (int)(Double.parseDouble(st.nextToken())*100+0.5);
                // dp[j]: j원으로 얻을 수 있는 최대 칼로리

                // p<=j<=m까지 탐색하며 j값일 때 최대 칼로리를 갱신
                for(int j = p; j <= m; j++){
                    dp[j] = Math.max(dp[j], dp[j - p] + c);
                }
            }
            System.out.println(dp[m]);

            // 다음 입력을 받기
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = (int)(Double.parseDouble(st.nextToken()) * 100+0.5);
        }
    }
}