백준 4781 사탕가게 - C++

www.acmicpc.net/problem/4781

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n, c;
int arr[10010];
pair<int, int> candy[5001]; // 칼로리, 가격 순
double m, p;

int main(){
    while (true){
        memset(arr, 0, sizeof(arr));
        // 돈 : m, n : 사탕의 종류
        cin >> n >> m;

        if(n == 0 && (m < 0.001))
            break;

        
        for(int i = 0; i < n; i++){
            cin >> c >> p;
            candy[i] = make_pair(c, (int)(p * 100 + 0.5));
        }

        
        int intM = (int)(m * 100 + 0.5);
        for(int i = 0; i < n; i++){
            for(int j = candy[i].second; j <= intM; j++)
                arr[j] = max(arr[j], arr[j - candy[i].second] + candy[i].first);
        }

        cout << arr[intM] << '\n';
    }
}

---

 이전에 풀이했던 냅색 문제라 생각해서 1차원 배열만으로 할려고 했지만 '같은 사탕을 여러개 선택'하는 경우가 있기 때문에 예제를제대로 뽑아낼 수 없었습니다.

 또한 이상하게 float을 인식하지 못하는것 같아 double로 해줬고 오차가 있다는 소식에 0.5를 추가해 반올림에서의 오차를 없애주었습니다.