절사평균( BOJ 6986 )

문제 : https://www.acmicpc.net/problem/6986

6986번: 절사평균

 

문제 파악하기

체조경기에서 사용하는 평균 계산법인 절사평균과 보정평균을 구하는 문제입니다. 다만, 입력이 실수로 주어지기 때문에 오차가 발생하기 쉽다는 점을 간과한다면 절대 풀 수 없는 문제입니다. 절사평균과 보정평균을 구하는 방법은 간단합니다. 모든 입력값을 정렬한 다음, 양 쪽의 K개 숫자를 없애거나(절사평균) K개 숫자를 인근 숫자로 변환(보정평균)한 다음, 평균을 구하면 됩니다. 쉬워보이지만 문제는 float 변수를 사용하여 입력받고, 그대로 평균값을 계산하면 오답이 나옵니다.

 

이는 컴퓨터가 사용하는 이진수 체계의 한계점입니다. 어떤 실수값을 이진수로 표현하기 위해서는 해당 실수값을 1/2, 1/4, 1/8, ... 등과 같이 2의 거듭제곱으로 만들어진 분수로 표현해야 합니다. 조금만 생각해봐도 문제가 생길 수 있다는 사실을 눈치챌 수 있습니다. 그렇기에 컴퓨터에서의 실수 계산은 항상 오차가 발생할 수 있다는 점을 명심해야 합니다.

 

그렇다면 이 문제는 실수 값을 계산해야 하는데 어떤 방법이 있을까요?

 

문제 해결하기

실수의 오차를 줄이는 방법은 여러 가지 있지만, 이번 문제에서는 가장 쉬운 방법을 사용하겠습니다. 실수값의 오차를 줄이는 가장 간단한 방법은 바로 실수값을 사용하지 않는 것입니다. 모든 값을 정수로 입력받고, 정수로 계산한 다음, 직접 반올림 알고리즘을 구현하면 됩니다. 다행히 이번 문제에서는 항상 소숫점 아래 첫 번째 자리까지만 주어집니다. 그렇다면 우리는 다음과 같이 입력을 받을 수 있습니다.

scanf("%d.%d", &a, &b); // a.b

이렇게 소수값을 2개의 정수로 나눠받은 다음에는 수식을 사용하여 정수 형태로 바꿔주면 됩니다. 그리고 우리는 소숫점 아래 3번째 값에서 반올림을 할 예정입니다. 그렇다면 입력되는 모든 값에 1000을 곱한 다음, 평균을 구할 때 정수의 나눗셈을 사용하면 됩니다. 그리고 직접 반올림 알고리즘을 구현하여 소수 형태로 출력하면 우리가 원하는 결괏값을 출력할 수 있습니다.

 

소스 코드

#include <stdio.h>
#include <algorithm>
#define NMAX 100010
 
int n, k, a, b;
long long int tot_a, tot_b, ave_a, ave_b;
 
int inp[NMAX];
 
int convert(long long int k) {
    if(k%10 < 5) return k/10;
    else return k/10 + 1;
}
 
void print(long long int p) {
    long long int a, b;
 
    a = p/1000; b = convert(p%1000);
    if(b == 100) a++;
    
    printf("%lld.%02lld", a, b%100);
}
 
int main() {
    // input
    scanf("%d %d", &n, &k);
    for(int i=0;i<n;i++) {
        scanf("%d.%d", &a, &b);
        
        inp[i] = (a*10+b)*100;
    }
    
    // sort
    std::sort(inp, inp+n);
    
    // tot_a: 절사평균 / tot_b: 보정평균
    for(int i=0;i<n;i++) {
        if(i<k) inp[i] = inp[k];
        else if(i>=n-k) inp[i] = inp[n-k-1];
        else tot_a += inp[i];
        
        tot_b += inp[i];
    }
    
    ave_a = tot_a/(n-2*k);
    ave_b = tot_b/n;
 
    // print
    print(ave_a); printf("\n");
    print(ave_b);
    
}

 

후기

간단한 문제이지만 실수의 오차 때문에 한참을 고민했던 문제입니다. 이진수에 대한 개념이 부족한 사람에게 추천하고 싶은 문제입니다.