[백준] 4781번 사탕가게 C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n,x;
double m,y;
pair<int, double> a[5003];
int dp[10003];

int main() {
    while(1) {
        cin >> n >> m;
        if(n == 0 && m == 0) break;
        fill(a, a+5003, make_pair(0,0));
        fill(dp, &dp[0]+10003, 0);
        for(int i = 0; i < n; i++) {
            cin >> x >> y;
            a[i].first = x;
            a[i].second = y;
        }
        for(int i = 0; i < n; i++) {
            for(int j = a[i].second*100 + 0.5; j <= (int)(m*100 + 0.5); j++) {
                dp[j] = max(dp[j], dp[j - (int)(a[i].second*100+ 0.5)] + a[i].first);
            }
        }
        cout << dp[(int)(m*100 + 0.5)] << '\n';
    }    
    return 0;
}

풀이

무난한 배낭문제...라고 생각했으나 소수점 오차를 고려하지 못해 틀린 문제다. 소수점 두 자리수까지만 주어진다고 해서 *100을 해주고 인덱스에 저장하게 했으나, 100을 곱하고 int형으로 캐스팅하는 과정에서 소수점 오차가 생긴 듯하다. 질문 게시판에서 해결 방법을 찾았다. int형으로 바꿀 때는 소수점 아래를 버리는데 대부분 정확히 나오지만 몇몇 수는 자연수보다 작게 나온다고 한다. 적당히 작은 수를 더해 소수점 아래를 버림하면 문제가 없다고 한다. 그래서 int형으로 캐스팅하는 부분에 모두 0.5를 더해주었고, 통과했다. 컴퓨터로 소수를 다룰 때는 항상 유의해야겠다.