[ boj : 14919 ] 분포표 만들기

 

www.acmicpc.net/problem/14919

14919번: 분포표 만들기

문제 : [0,1) 인 구간에서 m개의 구간으로 나누었을때 각 구간을 [b1,b2] [b2,b3] ..... [b(m-1),b(m)] 이라고 하자. 이때 주어지는 배열에서 각 구간에 포함되어 있는 개수를 구하여라

 

해설 : 음....너무 까다로운 문제였어요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ이게 어떻게 실3이냐!!!!

부동소수점의 개념을 알면 맘편히 풀 수 없는 문제죠. 흔히 실수형으로 0.3을 입력하면 0.3이 찍히지 않습니다.

이유는 컴퓨터는 정확한 소수점을 포함하는 실수를 표현하지 못하기 때문이죠.

즉, 오차가 항상 존재한다는 뜻입니다.

0.3을 입력하면 0.29999999999999999 이거나 0.30000000000001 이 됩니다.

그럼 이 문제를 낸 의도는 무엇이냐???라고 물으면 정확하지는 않지만

1)문자열로 입력을 받은후 파싱을 해라

2)부동소수점의 오차를 너가 잘 조정해라

가 아닐까 생각입니다.

 

전 2번으로 해결하였습니다. 문제에서 최대 소수점 6자리까지 입력이 주어진다 했으니 7자리에서 1을 더하면 원래 입력하려고 했던 값과 동일한 값으로 취급이 가능합니다. 무슨 말이냐면

0.3을 입력하면 0.29999999999~ 와 0.300000000~1 로 값이 들어가게 되고 7번째자리에서 1을 더한다면 

0.30000009999~ 와 0.3000000100~1 이 됩니다. 6째자리 아래로는 볼 필요도 없으니깐 밑에는 신경도 안써도 되겠죠.

 

이것을 이용해서 이분탐색을 통해 범위를 줄이면서 답을 도출했습니다.

 

#include<bits/stdc++.h>

using namespace std;

double arr[1000000];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int pos = 0;
	double m,x,n;

	cin >> m;
	x = 1 / m;
	while (true) {
		cin >> n;
		if (cin.eof()==true)break;
		arr[pos++] = n+0.0000001;
	}
	sort(arr, arr + pos);
	double s = 0, e = x;
	for (int i = 0; i < m; i++, s += x, e += x) {
		int l = 0, r = pos-1;
		int L=0, R=pos;		
		while (l <= r)
		{
			int mid = (l + r) / 2;
			if (arr[mid] < e) {				
				l = mid + 1;
			}
			else {
				R = mid;
				r = mid - 1;
			}
		}		
		L = lower_bound(arr, arr + pos, s)-arr;
		cout << R - L << " ";
	}
	return 0;
}

+더불어 이분탐색을 할 필요도 없습니다. 사실.....

오차를 조정해준 다음에 이를 정수형으로 치환해주어 그대로 출력하면 되기때문이죠.

어차피 m의 최대값은 1000이니까요...정말 아름답지 않나요?

djm03178 님의 코드입니다.

 

#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

int ans[1000];

int main()
{
	int m;
	scanf("%d", &m);
	double d;
	while (~scanf("%lf", &d))
	{
		d += 1e-9;
		ans[m * int(d * 1000000) / 1000000]++;
	}
	for (int i = 0; i < m; i++)
		printf("%d ", ans[i]);
}