[Python] 4411번 The Trip

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

4411번: The Trip

---

22/08/24

 

 

실버 랜덤 디펜스를 하던 도중 만난 문제이다.

 

 

문제에서 요구하는 사항은 다음과 같다.

 

---

 

문제 요약:

 

학생들이 여행을 가는데, 여행에서 나오는 비용을 더치페이하려고 한다.

 

근데, 비용이 나올 때마다 분배해서 지불하는 것은 여러모로 효율적이지 않으므로, 금액이 나올 때마다 한 사람이 다 지불한다. 그리고 나중에 학생들끼리 금액을 서로 주고받으려고 한다.

 

이때 주고받는 최소 금액은? (단, 1센트 단위 밑의 오차 허용)

 

---

 

초기 접근 방법:

 

일단 금액을 더치페이 하니깐... 당연히 평균을 내줘야겠다고 생각했다.

 

그 평균값은 당연히 3명이면 3명, 4명이면 4명 모든 학생들에게 청구되는 금액일 것이다.

 

"학생들끼리 금액을 주고받을 때 최소로 주고받으려면, 적게 낸 학생이 많이 낸 학생에게 그냥 돈을 주면 되겠네?"

라고 생각을 하고 (평균값) - (한 학생이 낸 금액)의 리스트를 구하여, 그 중에 양수인 애들(적게 낸 학생)의 리스트만을 만들어서 sum함수로 더해주었다.

 

그리고 출력을 했는데.... 틀렸습니다를 받았다.

 

---

 

이후 접근 방법:

 

1센트 단위 밑의 오차를 허용한다는 사실을 놓치고 있었다.

 

어떻게 보면 (평균 값) - (한 학생이 낸 금액)은 일종의 "편차"에 해당이 되는 셈인데, 이 편차가 음수라면 많이 낸 학생인 것이고, 이 편차가 양수라면 적게 낸 학생에 해당이 될 것이다.

 

일반적으로는, 이 편차들을 전부 합하면 0이 되는 것이 정상이지만, 나중에 금액을 주고받을 때 1센트 단위 밑은 거래를 하지 않으므로 편차 값은 센트 단위 이하로 기록되지 않는다.

 

그래서 편차 값이 반올림이 되고, 편차의 합은 0이 아닐 수도 있다....

 

또 다르게 말하면, 양수 편차의 합(많이 낸 학생들이 손해 본 금액)과 음수 편차의 합(적게 낸 학생들이 이득 본 금액)이 다를 수도 있다는 거다.

 

이걸 어떻게 알았냐면 예제 입력을 유심히 보고 알게 되었다.

4
15.00
15.01
3.00
3.01

두 번째 테스트 케이스가 다음과 같이 주어지는데, 그에 대한 결과는 11.99달러가 나온다.

 

평균값이 9.004999... 달러이고, 이에 대해 편차를 계산하는데 1센트 밑으로는 거래를 하지 않으므로 각 편차들의 리스트는 다음과 같다.

[-6.0, -6.01, 6.0, 5.99]

다 더해보면 0이 나오지 않는다.

 

때문에 어쨌든 간에  적게 낸 학생이 많이 낸 학생에게 금액을 줘야 되는 것은 사실이지만, 얼마를 줄지가 관건이다.

 

많이 낸 학생의 편차의 크기만큼 적게 낸 학생이 많이 낸 학생에게 금액을 줄지,

적게 낸 학생의 편차의 크기만큼 적게 낸 학생이 많이 낸 학생에게 금액을 줄지.

 

 

문제에서 요구하는 사항은 최소 거래량을 요구하므로, 둘 중 최솟값을 구하면 그것이 답이 된다.

 

---

 

이하는 내가 파이썬으로 작성한 코드이다. 더보기를 누르면 확인할 수 있다.

# 4411번 The Trip
# 그리디, 구현
while True:
    n = int(input())
    if n == 0:
        break
    expenses = [float(input()) for _ in range(n)]
    avg = sum(expenses)/n
    value_1 = sum(filter(lambda x: x>0, [round(avg - i, 2) for i in expenses]))
    value_2 = sum(filter(lambda x: x>0, [round(i - avg, 2) for i in expenses]))
    print(f'${min(value_1, value_2):.2f}')