[BAE/<JOON> 문제풀이] 4781. 사탕 가게

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

4781번: 사탕 가게

서론

아무리봐도 코드가 맞는데 틀려서 검색해보니 컴퓨터가 실수를 다루는 방식을 몰랐었다. 

---

풀이

그냥 배낭 문제다.

그런데 특이하게도 가격이 실수다. 소수부분 길이는 2로 고정되어있기 때문에 100을 곱하기만 하면 정수로 바꿀 수 있을 거라 생각했다. 하지만 내가 회사 프로젝트를 하면서도 가끔 봤던 현상인데 실수를 처음 초기화 할때는 값에 문제가 없다가도 몇번 연산을 거친 뒤에 보면 1.0으로 나와야할 값이 0.999999999999..998 이 되어있는 현상이 있었다.

 

이는 반올림 오류 ( Rounding-off Error ) 라고 하는 오류다.

실수는 아날로그처럼 조밀성을 갖지만 컴퓨터는 0과 1로 이루어진 비트만으로 연산하기 때문에 ( 이산성 ) 실수의 조밀성을 절대 정확하게 표현할 수 없다. 따라서 양자화를 통해 표현할 범위를 제한하여 표현한다. 실수 계산 과정에서 정보가 유실되며 발생한다는데 PS 관련 내용도 아니니 여기까지만 적겠다.

 

PS 할 때 해결 방법은 그냥 +0.5 하고 반올림 하면 된다. 

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct can {
	int cal, cost;
};
int main() {
	while (true) {
		int n; double tmp; int m;
		cin >> n >> tmp; m = (int)(tmp * 100 + 0.5);
		if (n == 0 && m == 0) break;
		vector<can> arr(n + 1); vector<int> dp(m + 1);
		for (int i = 1; i <= n; i++) {
			int t1; double t2;
			cin >> t1 >> t2;
			arr[i].cal = t1; arr[i].cost = (int)(t2 * 100 + 0.5);
		}
		for (int i = 1; i <= n; i++) {			
			for (int j = arr[i].cost; j <= m; j++) {
				int s1 = dp[j - arr[i].cost] + arr[i].cal;				
				dp[j] = dp[j] > s1 ? dp[j] : s1;
			}
		}
		cout << dp[m] << "\n";
	}
	return 0;
}