문제 링크

https://www.acmicpc.net/problem/14919

사용 언어

C++

소스

#include <iostream>
using namespace std;
  
int main()
{
	int m;
	scanf("%d", &m);
	int B[m] = {0,};
	double num;
	while(~scanf("%lf", &num)) B[(int)(m*num+0.0000001)]++;
	for(int i = 0; i < m; i++) printf("%d ", B[i]);
}

논리

1 <= k <= m 에 대해, 배열 B의 각 원소값을 다음과 같이 정의하자. \(B[k-1]=\left|\left\{a_n \in \left[ \frac{k-1}{m},\ \frac{k}{m}\right)\right\}\right|\)

분명 아래의 주장은 참이다.

따라서 아래와 같은 사실을 얻을 수 있다.

m과 a_n은 양수 이므로 컴퓨팅적으로 다음과 같은 사실을 참으로 생각하자.

따라서 각 a_n을 입력 받을 때마다 B[(int)(m*a_n)]의 값을 1씩 증가시켜주면 된다.

컴퓨팅적 문제

분명 논리적으로는 완벽한데 계속해서 오답이 생길 것이다.

안타깝게도 컴퓨터가 이 세상 모든 수를 표현할 수는 없기 때문이다.

부동소수점의 원리를 이해 한다면

0.1을 입력하더라도 저장되는 값은 0.1보다 크다는 것을 알 것이다.

또한 0.3을 입력하더라도 저장되는 값은 0.3보다 작다.

자, 그럼 어떤 경우에 오류가 생기는지 구체적인 예를 보자.

m = 625라 하자. a_n = 0.0048 이라면 625 * 0.0048 = 3 이므로

논리적으로 B[3]에 카운트가 되어야 함을 알 수 있다.

그런데 0.0048의 부동소수점으로 표현된 값은 0.00479999999999999957950.. 이다.

그 결과 625 * 0.0048 = 2.99999999999999955591079.. 이며

(int)(m*a_n) = 2가 되어 논리적으로 예상한 값과 다르게 나오는 것을 확인할 수 있다.

따라서 문제사황을 다음과 같이 정리할 수 있다.

“m*a_n의 논리적인 계산값을 x라 하면 부동소수점에 의한 계산값은 x + e 이다.”

(-10^-7 < e < 10^-7)

그리고 해결방법은 다음과 같다. x + e에 10^-7을 더하는 것이다.

그 이유를 아래와 같이 보일 수 있다.