10137 : The Trip

문제 : http://goo.gl/p7Pso

부동소수점의 연산은 최대한 피해야 한다는 것을 알려준 문제.
10분만에 풀줄 알았는데, 연산결과의 정확성이 떨어지는 것을 발견하고 이를 교정하는데 상당히 오랜 시간이 걸렸지만 결국 실패했다.

연산은 int형으로 하기로 결심했다. 이를 위해서는 먼저 (double변수*100+0.5)의 반올림 과정이 필요하다. (float으로 할 경우 1000명*10000달러의 데이터 합을 감당해 내지 못한다. -의외였다.)
그리고  사람수로 나눈 몫은  avg가 되고, 나머지는 돈을 많이낸사람에게 1원씩 배분해주어야 한다.(int로 변환한 뒤 1원. 본 문제에서는 1cent가 되겠다.)
많이낸 순서를 알기 위해서는 Sorting이 필요하고, 이는 qsort로 해결하였다.
(qsort 사용시 비교함수 만드는 법정도는 암기해두어야 겠다.)
평균의 차이를 계속 더해주고, 돈을 많이 낸 사람은 기존 평균에서 +1원한 뒤 계산한다.
그리고 다 더한 sum을 2로 나눠준다.( 그 이유는 분배한 돈중 주는 돈과 받는 돈을 중복적으로 계산 하였기 때문이다.) 이제 출력을 위해 100으로 나눠주어야 한다.

while(true)
 {
  int people;
  int ave=0, remnant;
  double sum=0.0;
  int pay[1000];
  
  scanf("%d", &people);
  if( people==0) break;

  REP(i, people)
  {
   double tmp;
   scanf("%lf",&tmp);
   pay[i] = (int)(tmp*100+0.5);
   ave += pay[i];
  }
  remnant = ave%people; // 나머지
  ave /= people; // 평균
  qsort(pay, people, sizeof(int), comp);
  
  REP(i, people-remnant)    sum += abs(pay[i]-ave);
  for(i=people-remnant; i<people; i++)sum += abs(pay[i]-(ave+1));
  printf("$%.2f\n",(sum/2.0)/100.0);
 }
int comp(const void *a, const void *b)
{
 if(*(int*)a<*(int*)b) return -1;
 else if(*(int*)a>*(int*)b) return 1;
 else return 0;
}