[홍대코딩대회/부동소수점] 14919번 분포표 만들기

쉬운 문제 같은데 부동 소수점 오차 때문에 한 15번 넘게 틀린거 같다..

double형 변수에 어떤 값을 넣을때 0.3이란 실수를 넣게 되면 0.300000000으로 정확하게 들어가는게 아니라 0.2999998888 또는 0.300000000001등과 같이 약간 오차가 있게 값이 들어가기 때문에 이것을 해결해주어야 한다.

0~1의 구간을 6개로 나눈다 했을때, 

0 <= 구간1 < 1/6 = 0.16666666666...

1/6 <= 구간2 < 2/6 = 0.333333333...

2/6<= 구간3 < 3/6 = 0.5 (정확히 0.5)

3/6<= 구간4 < 4/6 = 0.666666666...

4/6<= 구간5 < 5/6 = 0.833333........

6/5 <= 구간6 < 6/6 = 1(정확히1)

IEEE 표준에 의해서 컴퓨터는 실수를 표현할때 1.xxxx(가수부) * 2^(지수부) 의 형식으로 표현하기 때문에 2의 배수는 정확하게 표현할수 있지만 2의 배수가 아닌 다른 10진수 또는 소수에 대해서는 정확한 값이 아닌 근사값으로 표현하게 된다. 이점을 잘 알아야 하는 함정이 숨어있다.

double또는 float 변수에 넣은 값이 내가 넣은 값과 정확히 일치하지 않는 다는것을 알아야 한다.

우선 구간을 나누려면 어쩔수없이 double형 변수 하나를 사용해야 한다. 그래서 나는 오차를 줄이기 위해서 더블형 변수에 0.0000000001를 더해줬다. 구간을 최대 1000개 까지 나눌수 있고 문제에서 소수 6번째 자리 까지 수가 주어질수 있기 때문에 6자리 +3자리 더해서 소수점 9번째 자리 까지는 수가 정확해야 한다. 그래서 10번째 자리에 1을 더해준다음에 int형 변수로 바꿔주면 버림을 하기 때문에 내가 더블형 변수에 넣으려고 의도한 값이 소수점 9번째 자리 까지는 정확하게 들어간다.

n이 6이라고 할때

먼저 1을 구간의 개수로 나눈 1/n을 하게 되면 대략 0.1666666666...이라는 숫자가 나오는데 이것을 정수로 바꾸기 위해서 1000000을 곱하게 되면 166666.666666 이라는 숫자가 나오게 될것이다. 다시 말해서 깔끔한 정수가 아닌 소수이다. 이런 경우 0.166666이 인풋으로 들어왔을때 구간1의 숫자로 판단을 해야 한다. 왜냐면 166666.666666.......보다 0.166666에 100만을 곱한 166666.00000...이 더 작기 때문이다.

백만을 곱했을때 소수가 아닌 정수가 나올것인가 아니면 소수가 나올것인가 판단하는 방법은 if(((i+1)*1000000) % n != 0)

이 if문이다. 100만/6 했을때 나머지가 남기 때문에 깔끔하게 나눠 떨어지지않는 뜻이고 그 뜻은, 1/6 = 0.166666......에 백만을 곱했을때 166666.666666......등과 같이 소수가 된다는 의미이다. 그렇기 때문에 경계를 정수로 나타냈을때

첫번째 구간은 0~166667보다 작은 숫자를 모두 카운트 해야한다.

두번째 구간은 166667에서 또 어떤 숫자 까지인데,

이 숫자를 구하는 방법은 200만%6 했을때 나머지가 존재하므로 깔끔하게 떨어지지 않는다. 따라서 1/6 = 0.166666.... 에 2를 곱하고 -> 0.333333.... 여기에 다시 백만을 곱하게 되면 333333.33333이다. 여기서 버림을 하게 되면 333333이란 숫자가 나오고, 경계는 333333이 아닌 333334이 되어야 한다. 왜냐면 333333.3333333....가 두번째 구간의 오른쪽 경계값인데 우리는 이 실수 경계를 정수 경계로 바꾼다음 판단할것이기 때문에 333333이란 정수도 2번째 구간에 포함되어야 한다.

그렇기 때문에 나눴을때 깔끔하게 떨어지지 않으면 정수형 경계값에 +1을 해주어야 한다.

만약에 그다음 구간인 구간3같은 경우에는 3 * 백만%6 = 0(깔끔하게 나눠 떨어진다)

그렇기 때문에 구간도 그냥 0.5에 백만을 곱한 500000이 될것이다.  즉 333334~499999 까지의 정수가 구간3에 들어가야 한다.

소스코드

#include<iostream>

#include<stdio.h>

#include<math.h>

using namespace std;

int n;

int main(){

    cin>>n;

    double x;int m;

    

    int* div = new int[n];

    int* result = new int[n];

    

    double d = (double)1/n+0.0000000001;

    for(int i=0; i<n; i++){

        div[i] = (i+1)*d*1000000;

        if(((i+1)*1000000) % n != 0) div[i]++;

    }

    

    while (~scanf("%lf", &x)) {

        x += 0.0000000001;

        m = x*1000000;

        for(int i=0; i<n; i++){

            if(m < div[i])

            {

                result[i]++;

                break;

            }

        }

    }

    

    for(int i=0; i<n; i++)

        cout<<result[i]<<" ";

    cout<<endl;

    

    return 0;

}