백준 - 4781번 : 사탕 가게 (C++)

풀이 방법 : DP

매우 매우 전형적인 가방채우기 DP 문제이다.
아이디어를 떠올리는 것과 구현 자체는 쉬우나 실수형의 자료를 정수형으로 캐스팅 하는 과정에서 발생하는 rounding error를 생각하지 못해서 헤맬 가능성이 많은 문제다.
보통 정수형 캐스팅을 하기 전에 0.5를 더해주는 식으로 반올림에 의한 오차를 보정해주는 방법이 있다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const float bias = 0.5f;

struct Candy
{
	int Price = 0;
	int Calorie = 0;
};

int main()
{
	while (true)
	{
		int N = 0;
		float fMoney;
		int iMoney = 0;

		cin >> N >> fMoney;

		if (N == 0)
			break;

		iMoney = (int)(100 * fMoney + bias);

		vector<Candy> vecCandy(N);

		for (int i = 0; i < N; ++i)
		{
			float fPrice;
			cin >> vecCandy[i].Calorie >> fPrice;
			vecCandy[i].Price = (int)(fPrice * 100 + bias);
		}
		
		vector<int> DP(iMoney + 1);

		int Max = 0;

		for (int i = 1; i <= iMoney; ++i)
		{
			DP[i] = DP[i - 1];

			for (int j = 0; j < N; ++j)
			{
				int Money = vecCandy[j].Price;

				if (i - Money >= 0)
				{
					DP[i] = max(DP[i], DP[i - Money] + vecCandy[j].Calorie);
				}
			}

		}

		cout << DP[iMoney] << '\n';

	}
}

컴퓨터에서 실수를 완벽하게 표현할 수 있는 수단은 없다는 점,
따라서, 실수를 사용할 때에는 오차를 고려해야 한다는 점을 명심하자.