BOJ : https://www.acmicpc.net/problem/4411
실수를 표현하는 방법 1)과 값을 최소화하기 위한 방식 2)을 알면 해결할 수 있는 문제입니다.
기본적으로 실수를 정수로 바꿔주는 캐스팅 과정에서
원하는대로 정확히 변경되지 않습니다.
double num 에 1.01을 입력받는 경우 디버깅으로 확인해보면 1.009999... 라는 값을 가지게 됩니다.
실수를 정수로 변환하는 과정에서 가장 간단한 방법은 0.5를 이용하는 것입니다.
이 문제는 계속 실수만 가지고 계산하다가는 정확한 값을 얻을 수 없을 것 같아서 아예 정수로 바꿔놓고 계산했습니다.
2번째 자리까지에 대한 값만 알면 되므로 정수 = 실수*100+0.5 로 캐스팅하여 이용했습니다.
풀이과정은 다음과 같습니다.
총 금액에 대한 평균을 구할 수 있고, 모든 사람은 최소한 평균이상의 금액은 지불해야 합니다.
이 때 총 금액을 인원수에 맞게 나누었을 때 나머지**)는
"정확히 나눌 수 없으니 서로 1센트 정도는 더 내서 채워야되는 금액" 을 의미합니다.
그럼 필요한 정보들은 다음과 같아집니다.
1) 현재 사람들이 낸 금액
2) 현재 사람들이 내야할 금액
2) 현재 사람들이 내야할 금액은 기본적으로 총금액에 대한 평균값은 모두 가져야 할 것이고,
나머지**) 를 이용해서 2)의 값을 다시 계산해주면 됩니다.
결국 정답은 1) - 2) 또는 2) - 1) 에 대한 값이 되는데
중요한 것은 내야할 금액을 최소화 (돈을 많이 낸 사람이 돈을 최대한 돌려받는 경우) 하는 것입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int total;
int person;
double p;
vector<int> pay, real_pay;
cin >> person;
while (person) {
total = 0;
for (int i = 0; i < person; i++) {
cin >> p;
pay.push_back(p * 100 + 0.5);
total += pay[i];
}
int indivi = total / person;
int mod = total % person;
total = 0;
sort(pay.begin(), pay.end(), greater<int>());
for (int i = 0; i < person; i++) real_pay.push_back(indivi);
for (int i = 0; i < mod; i++) real_pay[i]++;
for (int i = 0; i < person; i++) total += abs(real_pay[i] - pay[i]);
cout << fixed;
cout.precision(2);
cout << "$" << (total / 2) / 100.0 << "\n";
cin >> person;
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
'algorithm > uva' 카테고리의 다른 글
| uva 10150번 Doublets (0) | 2020.03.27 |
|---|---|
| uva 10469번 To Carry or not to Carry (0) | 2020.03.23 |
| uva 10010번 Where's Waldorf? (0) | 2020.03.23 |
| uva 679 - Dropping Balls (0) | 2020.03.19 |
| uva 100 - 3n+1 problem (0) | 2020.03.18 |