The Trip

Problem A: The Trip

A number of students are members of a club that travels annually to exotic locations. Their destinations in the past have included Indianapolis, Phoenix, Nashville, Philadelphia, San Jose, and Atlanta. This spring they are planning a trip to Eindhoven.

The group agrees in advance to share expenses equally, but it is not practical to have them share every expense as it occurs. So individuals in the group pay for particular things, like meals, hotels, taxi rides, plane tickets, etc. After the trip, each student's expenses are tallied and money is exchanged so that the net cost to each is the same, to within one cent. In the past, this money exchange has been tedious and time consuming. Your job is to compute, from a list of expenses, the minimum amount of money that must change hands in order to equalize (within a cent) all the students' costs.

The Input

Standard input will contain the information for several trips. The information for each trip consists of a line containing a positive integer, n, the number of students on the trip, followed by n lines of input, each containing the amount, in dollars and cents, spent by a student. There are no more than 1000 students and no student spent more than $10,000.00. A single line containing 0 follows the information for the last trip.

The Output

For each trip, output a line stating the total amount of money, in dollars and cents, that must be exchanged to equalize the students' costs.

Sample Input

3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
0

Output for Sample Input

$10.00
$11.99

//---------------------------------------------------------------------------------------------------------------------------------------------------------------------//

문제를 간단히 보면, 첫 입력으로 학생 수가 들어오고, 그 아래로 학생 수만큼의 지출금액이 나온다. 0이 나오면 프로그램이 종료된다. 출력은

각 여행마다 공평하게 지출금액을 나누기 위해 교환해야되는 금액을 출력하는 것이다.

문제는 정말 간단하다. 근데 아직까지 문제를 풀진 못했다. 뭐가 잘못인지.

처음 생각한 것은, 평균 금액을 구하는 것이다. 총 지출을 다 더한 뒤에, 학생 수만큼 나눈다. 여기서 소수점 셋째자리 이하는 버린다. 예로

15+15.01+3+3.01을 더해서 4로 나누면, 9.005가 나온다. 이때 0.005를 버리고 9.00만 가진다.

그리곤 이 평균 금액보다 적게 지출한 인원들은 평균-지출한 금액을 해서 그만큼을 더 내는 것으로 생각했다.

예로 보면,

첫 예시인 10,20,30 의 금액을 지출했을 때, 평균을 구하면, 20이다. 20보다 적게 낸 금액은 10밖에 없고, 20-10은 출력인 $10.00이 나온

다 .

다른 예시인 15,15.01, 3, 3.01로 보면, 평균은 9.005에서 9.00만 사용하여, 이 값보다 작은 금액인 3, 3.01을 뺀다.

9 - 3.00 + 9 - 3.01 = 11.99이다. 이 값 또한 예시로 나온 출력 값과 동일하다.

이렇게 코딩을 해서 결과를 검사 받았더니, "Wrong Answer"이라고 나온다. 어떤 것을 놓친건지.

소숫점 셋째자리를 버림 하는 것이 아니라, 올림을 해야하는지, 반올림을 해야하는지 조금 더 시도를 해봐야겠다. 예시가 조금 더 있으면 좋겠

다.

//---------------------------------------------------------------------------------------------------------------------------------------------------------------------//

개인적인 생각이지만, 이 문제는 정말 몇 안되는 똥 문제 중에 하난 것 같다.
여러가지 시도를 해봐도 안되길래 답지를 확인했다.

간단하게, 많이 낸 사람에게 더 많은 돈을 지불하게 하는 방법으로,

예제 케이스에서 4 15 15.01 3 3.01이 들어왔을 경우, 총 합은 36.02, 평균은 9.005이다.

이럴 경우, 평균에서 버림을 하여 9로 계산한다. 평균에 다시 학생 수를 곱하면 36.00이 나오고 총합에서 0.02가 모자르다.

남는 0.02를 가장 많이 지출한 사람들부터 내도록 0.01씩 나누어 분배한다. 이를 위해 내림차순으로 정렬하여

15.01 15 3.01 3 으로 만든 후에,

15.01 - 9.01 + 15 - 9.01 - ( 3.01 - 9 + 3.01 - 9)를 계산한다.

위 식은 평균 값보다 많이 낸 사람과 적게 낸 사람의 차는 항상 0이 되야 하는 것에서 나온다. 

평균보다 많이 낸 사람 = 평균보다 적게 낸 사람 

-> 평균보다 많이 낸 사람 - 평균보다 적게 낸 사람 = 0

어쨋건, 실제로 교환해야 하는 금액은 더 낸 사람은 평균보다 더 낸 만큼 돈을 받아야 하고, 적게 낸 사람은 그 만큼 더 돈을 내야한다.

따라서, 이 금액에 나누기 2를 한 금액이 실제로 교환해야 하는 금액이 된다.

그러나.. 정말 여러가지 케이스를 확인해봤는데 어질하다.

0.017 0.007 0.007이 입력으로 들어오면 출력이 $0.00 이 나와야 한다. 한 케이스를 잡았다고 생각해서 조금 수정 후에 다시

0.01 0.005 0.01 로 확인해 봤다. 답과 출력이 다르다.

해답을 보니, 해답에서는 input이 오는 것을 정수로 변환 한 후에 계산했다. 출력할 때만 다시 소수로 변환했다. 해답을 곰곰히 보니, 이렇게

안하면 답이 안나오는 경우가 꽤 많은 것 같다. 머리가 아파온다.

똥문제다.