문제 3 : 여행 ( The Trip )

PC/UVa ID : 110103/10137, 인기도 : B, 성공률 : 보통, 레벨 : 1

친구들 4명이서 음식점에 갔다. 그리고 음식을 시킨다. 난 짜장면, 난 짬뽕, 난 탕수육, 난 깐풍기, 이렇게 각자 원하는 것을 시켰다. 그리고 서로 사이 좋게 나누어 먹었다.  식사를 끝맞친 친구들은 계산을 하기 위해서 계산대 앞에 갔다.

계산대를 보던 사람이 짜장면 2500원, 짬뽕 3000원, 탕수육 6000원, 깐풍기 8000원, 이렇게 나왔다고 했다. 친구들은 한 사람에게 모든 돈을 주고 계산하라고 했다. 계산 후, 각자 집으로 돌아갔다. 그리고 학교에서 만난 이 친구들은 어제 맛있게 서로 나누어 먹었는데, 각자 평등하게 돈을 내는게 좋겠다고 이야기를 하였다.

각자 낸 금액에서 주거니 받거니를 계산하니, 너무 복잡했다. 짜장면을 먹은 녀석에겐 2375원을 더 받아야 하고, 짬뽕을 먹은 녀석에겐 1875원을 더 받아야 하며, 탕수육을 먹은 사람에겐 1125원을 돌려줘야 하고, 깐풍기를 먹은 녀석에겐 3125원을 돌려줘야 한다.

이런 상황에서 최소한 얼마 만큼 돈을 주거니 받거니 하면, 서로 평등하게 돈을 지출한 것이 되는가?

입력
식사에 참여한 n 명을 받고, 각 지출된 금액을 입력 한다. 학생 수는 1000 명을 넘지 말아야 하며, 어떤 학생도 10000원 이상 짜리의 음식을 먹지 못한다고 가정한다. 0이 입력되면 프로그램이 종료 된다.

출력
돈을 주거니 받거니 했을 때, 최소한 얼만큼이 이동되어야 서로 평등한 금액이 되는가?

입력 예)    출력 예)
3                         1000
1000
2000
3000

4                        1199
1500
1501
300
301

0                        정상 종료


총평
말이 좀 어려울 뿐이다. 이 알고리즘의 핵심은 평균에서 미달되거나 초과되는 한쪽만 계산하는 것 이고, 이번 문제는 이 알고리즘을 깨우치는 것에 있다. 예를 들어보자. 두 컵에 서로 다른 량 만큼 물이 들어 있다. 둘다 똑같은 물의 량으로 맞추려면, 얼만큼 물을 서로에게 부어야 하는가?

A 만약 두 컵의 물을 다른 한곳에 몰아 두고, 서로 똑같이 나눈다면, "한 곳에 몰아두는 작업" 과 "서로 똑같이 나누는 작업" 이 두번을 해야만 한다. B 만약 두 컵에서 물의 량이 많은 컵쪽에서 적은 쪽으로 부은다면, "서로 똑같이 나누는 작업" 만 하면 될 것이다.

물론 A와 B의 "서로 똑같이 나누는 작업"은 다르겠지만, "메모리" 라는 측면에서 본다면, 더 괜찮은 방법일 것이다. : ) 뭐 그래도 요즘은 별 상관없지만.. 메모리 2G 쯤이야.. 뭐 2만원이면 사지 않는가?

function main() while true do -- 인원수 입력 NumberOfPerson = io.read( "*number" ) -- 만약 0 이라면 종료 if 0 == NumberOfPerson then print("정상 종료") break end -- 인원수 예외 체크 0 < NumberOfPerson < 1000 if true == ( 0 > NumberOfPerson or 1000 < NumberOfPerson ) then print("인원수 예외 체크 0 < NumberOfPerson < 1000") break end -- 각각 얼만큼 지출했는지 입력 local i = 1 local Total_Payment = 0 local Each_Payment = { } while i <= NumberOfPerson do local Payment = io.read( "*number" ) -- 지출 금액 예최 체크 0 < Payment < 10000 if true == ( 0 > Payment or 10000 < Payment ) then print( "지출 금액 예최 체크 0 < Payment < 10000" ) return end -- 총 금액 누적 Total_Payment = Total_Payment + Payment -- 개별 금액 저장 Each_Payment[#Each_Payment + 1] = Payment i = i + 1 end -- 평균 금액 누적 local Average_Payment = Total_Payment / NumberOfPerson -- 개별 금액 내림차 정렬 table.sort(Each_Payment) local i = 1 local Transmission_Payment = 0 while i <= #Each_Payment do -- 평균보다 큰 쪽부터는 계산하지 않는다. -- 왜냐하면 평균보다 작은쪽만 계산해도 되기 때문이다. if Average_Payment <= Each_Payment[i] then break end -- 전달 금액 누적 Transmission_Payment = Transmission_Payment + Average_Payment - Each_Payment[ i ] i = i + 1 end print("전달되어야 할 최소 금액 : " .. Transmission_Payment ) end end main()