C언어 200제] 여행(The Trip)

출처 : 반크_백제역사 유적지구 및 이스탐블역사 유적지구

 

문제]

일년에 한 번씩 다른 여행지로 여행을 가는 학생 모임이 있다. 그 학생들은 지금까지 인디애나폴리스, 피닉스, 내시빌, 필라델피아, 산호세, 아틀란타를 여행했다. 이번 봄에는 아인트호벤으로 여행을 갈 계획이다.

이 학생들은 여행 경비를 모두 똑같이 부담하기로 합의했지만 돈을 쓸 때마다 나눠서 내는 것은 별로 실용적이지 못하다. 그래서 한 명씩 식비, 호텔비, 택시비, 비행기표를 부담하기로 한다. 여행이 끝난 후에 각 학생이 지출한 내역을 계산한 다음 1센트 단위 내에서 모든 학생들이 쓴 돈이 같도록 돈을 주고 받는다. 하지만 이전 여행의 경험에 비추어보면 돈을 주고 받는 과정은 정말 지루하고 오랜 시간을 요하는 작업이었다. 지출 내역이 주어졌을 때 모든 학생이 쓴 돈이(1센트 단위 내에서) 꼭같아지기 위해 전달되어야 하는 최소 액수를 구해보자.

입력
표준 입력을 통해 여러 번의 여행에 대한 정보가 입력된다. 각 여행은 여행에 참가한 학생 수를 나타내는 정수 n으로 구성된다. 이 정수 밑으로는 n개의 줄이 입력되는데, 각 줄에는 달러와 센트 단위로 각 학생이 지출한 경비가 입력된다. 학생 수는 1000명을 넘지 않으며 어떤 학생도 $10,000.00 이상 지출하지 않는다. 마지막 여행에 대한 정보 다음 줄에는 0만 들어있는 줄이 입력된다.

출력
각 여행에 대해 각 학생이 사용한 금액이 똑같아지기 위해 전달되어야 하는 금액의 총합을 출력한다.

입력 예
3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
0

출력 예
$10.00
$11.99

 

출처]

Programming Challenges 알고리즘 트레이닝 북(한빛미디어) : 문제3 여행(The Trip) p42

 

참고풀이]

#include <stdio.h>
#include <stdlib.h>

//각 사람별로 소모한 돈 
int money_spent[1000];
//최적의 경우에 각 사람이 지불해야 할 돈 
int money_must_spent[1000];

int main()
{
   int i,j,n;
   int tmp;
   int all_money_spent;
   int each_money_spent;
   int money_exchange;
   double cost;

   while(1)
   {
      all_money_spent=0;
      money_exchange=0;

      //인원수를 입력을 받는다.
      scanf("%d",&n);
      if(n==0) break;
      for(i=0;i<n;i++)
      {
         scanf("%lf",&cost);//인원수의 경비를 입력받는다.
         money_spent[i]=(int)(cost*100+0.5);
         all_money_spent += money_spent[i];
      }

      //돈을 가장 많이 쓴 사람부터 순서대로 나열한다.
      for(i=0; i<n-1; i++)
         for(j=i+1; j<n; j++)
            if(money_spent[i]<money_spent[j])
            {
               tmp=money_spent[i];
               money_spent[i]=money_spent[j];
               money_spent[j]=tmp;
            }

      //각 사람별로 얼마나 돈을 써야 최적화되는 지를 계산해 준다.
      each_money_spent = all_money_spent / n;
      for(i=0; i<n; i++)
         money_must_spent[i]=each_money_spent;

      all_money_spent %= n;
      for(i=0; i<all_money_spent; i++)
         money_must_spent[i]++;

      //각 사람별로 차액을 더해주면 결과가 나온다.
      for(i=0; i<n; i++)
         money_exchange += abs(money_spent[i] - money_must_spent[i]);
      money_exchange /= 2;

      //결과출력 
      printf("$%.2lf\n",money_exchange / 100.);
   }

   return 0;
}

 

참고풀이 결과]

 

 

 

 

 

대한민국의 아름다운 영토, 독도의 가을