ACM 10137, The Trip

http://acm.uva.es/p/v101/10137.html

 

더치 페이를 하면서, 가장 금액을 적게 교환하는 방법을 택해야 한다.

 

각자 낼 금액은 다음과 같이 구한다. 일단 평균을 구한다. 낼 금액 - 평균 * 사람 수 = 남은 거스름 돈. 이때 거스름이 사람 수로 나누어 떨어지지 않을 경우가 있다. 이때의 거스름돈 금액은 사람 수보다 작다. 남은 거스름돈은 돈을 많이 낸 사람 순으로 나눠준다.

 

많이 낸 사람이 1센트라도 더 내게 산정해놓는 이유는 다음과 같다, 돈을 적게 낸 사람이 많이 낸 사람에게 주는 금액이 1센트라도 적어지기 때문이다. 문제는 최소 교환 금액을 원하므로, 선불로 많은 금액을 내었는데도 불구하고(?) 1센트 더 내는 건 어쩔 수 없게 된다.

1135867852_The Trip.cpp