UVa Online Judge 10137. (The Trip)

< 문제 경로: https://uva.onlinejudge.org/external/101/10137.pdf >

일단 이 문제도 알고리즘 트레이닝 북 42페이지에 있는걸 보고 가볍게 풀려했으나,

알덕력이 모자라서 소수점에서 한참 헤매게 됐다.

나는 보통 소수점과 관련된 문제라면 int로 바꿔서 많이 풀었는데,

오늘은 int로 바꾸는 과정에서 문제가 있었다.

일단 컴퓨터는 부동소수점으로 소수를 표현하기 때문에 뭔가 문제가 많다.

소수와 관련된 연산은 결합법칙, 분배법칙도 성립하지 않고,

0.1은 사실상 정확히 표현이 불가능하며,

int(278.78 * 100)을 printf로 찍어보면 27877이 나오는 신비한 경험도 할 수 있다.

(이 부분은 int(278.78 * 100 + 0.5)로 해결할 수 있긴하다.)

문제는 이것말고도 상당히 많은데,

결론은.. 소수로 들어오는 input 데이터는 웬만하면 정수로 받자는 것이다.

#include <stdio.h>
int main() {
    double a;
    scanf("%lf", &a); //X
 
    int x,y;
    scanf("%d.%d", &x,&y); //O
}

물론 언제나 예외사항은 있지만,

소수 계산은 조심.. 또 조심..

10137 문제는 사람 수 N이 주어지고,

N개수만큼 달러값이 input으로 들어온다.

이 달러를 N명이 모두 골고루 나눠 갖을 때,

달러를 최소한만 이동시켜서 모두 골고루 나눠 갖으려한다.

모두 달러를 나눠 가졌을 때 1센트는 차이가 날 수 있다.

그럼 나는 N명의 달러 합을 sum이라 하고,

sum = a*q + b*(q+1)이 되는 a,b를 구했다.

여기서 q는 달러로.. N명중 a명은 q달러를 갖고, b명은 q+1달러를 가질 것이다.

그럼 q값은 int(sum/N)으로 구할 수 있고,

b값은 sum%N으로 구할 수 있다.

a = N-b이므로

이동시킬 최소 달러 값을 계산할 수 있다.

코드는 아래와 같다.

(정렬을.. 그냥 count sorting으로 해봤다.)

#include <stdio.h>
const int mask = (1<<10)-1;
int v[1001], cnt[mask+1], idx[2][mask+1];
inline int abs(int x) { return x<0?-x:x; }
int main() {
    while(true) {
        int n, sum=0; scanf("%d", &n);
        if(n==0) break;
 
        for(int i=0; i<n; i++) {
            int x,y; scanf("%d.%d",&x,&y);
            v[i]=x*100+y;
            sum += v[i];
        }
 
        //count sorting start
        for(int i=0; i<=mask; i++) cnt[i]=0;
        for(int i=0; i<n; i++) cnt[v[i]&mask]++;
        for(int i=1; i<=mask; i++) cnt[i]+=cnt[i-1];
        for(int i=n-1; i>=0; i--) idx[0][--cnt[v[i]&mask]] = i;
 
        for(int i=0; i<=mask; i++) cnt[i]=0;
        for(int i=0; i<n; i++) cnt[(v[i]>>10)&mask]++;
        for(int i=1; i<=mask; i++) cnt[i]+=cnt[i-1];
        for(int i=n-1; i>=0; i--) idx[1][--cnt[(v[idx[0][i]]>>10)&mask]] = idx[0][i];
 
        for(int i=0; i<=mask; i++) cnt[i]=0;
        for(int i=0; i<n; i++) cnt[v[i]>>20]++;
        for(int i=1; i<=mask; i++) cnt[i]+=cnt[i-1];
        for(int i=n-1; i>=0; i--) idx[0][--cnt[v[idx[1][i]]>>20]] = idx[1][i];
        //count sorting end
 
        int q=sum/n, r=sum%n;
        int a=n-r, ans=0;
 
        for(int i=0; i<a; i++) {
            if(v[idx[0][i]]<q) ans+=q-v[idx[0][i]];
            else break;
        }
        for(int i=a; i<n; i++) {
            if(v[idx[0][i]]<q+1) ans+=q+1-v[idx[0][i]];
            else break;
        }
        printf("$%d.%02d\n", ans/100, ans%100);
    }
    return 0;
}