[C언어 기출문제&풀이] 여행(the trip)

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

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

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

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

풀이: 돈의 단위에 센트가 없는 경우는 아주 간단한 방법으로 금액의 평균을 구해 그 평균과 각 사람이 실제 쓴 금액의 차를 구해서 모두 더한 뒤, 그결과를 2로 나누면 된다. (2로 나누는 이유는 한사람이 주면 한사람이 받기 때문이다.)

아 참고로 qsort 함수는 void qsort(void *base, size_t nel, size_t width, int (*compare) (const void *, const void *)); 의 원형이고 이 함수는 주어진 배열의 맨앞에서 부터 nel 개의 원소를 정렬한다. 이배열의 각 원소는 width 바이트를 차지한다. 예를 들어 정수형 배열인 a의 원소 n개를 정렬하려면 qsort((void *)a,size_t(n),sizeof(int),compare)이라고 적으면 된다. 
여기서 오름차순으로 정렬하려면 다음과 같은 비교함수를 사용하면 된다.
int intcompare(int *i, int *j)
{
if(*i>*j) return 1;
if(*i<*j) return -1;
else return 0;
}
내림차순으로 정렬하려면 리턴값 1과 -1을 바꾸어 주면 된다. 그리고 이 함수에서는 qsort라는 이름에서 알 수 있듯이 퀵 정렬 알고리즘을 사용한다. 그러므로일일이 정렬함수를 구현하지 않고 qsort를 사용하는 것이 시간도 절약하고 오류도 줄이는 좋은 방법이다.

소스코드:
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 1000
#define MAX_MONEY 10000

int compare(const void *arg1,const void *arg2)
{
 int p1, p2;
 p1=*(int*)arg1;
 p2=*(int*)arg2;
 return (p2-p1);
}

int money_spent[1000];
int money_must_spent[1000];

int main()
{
 while(1)
 {
  int i,n;
  int all_money_spent=0;
  int each_money_spent;
  int money_exchange=0;

  scanf("%d",&n);
  if(n==0) break; 

  //각각 지출한 돈 입력
  for(i=0;i<n;i++)
  {
   double t;
   scanf("%lf",&t);
   money_spent[i]=(int)(t*100+0.5);
   all_money_spent+=money_spent[i];
  }

  // 오름차순 정렬
  qsort((void*)money_spent,(size_t)i,sizeof(int),compare);

  //달러 구하기
  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("$%.2f\n", money_exchange/100.0);
 }
}