취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14919번 문제인 분포표 만들기이다.
문제는 아래 링크를 확인하자.

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

주어지는 소수들은 소수점 여섯자리까지만 주어지고 모두 0보다 크며 1보다 작으므로, "0." 이후의 소수점 첫째자리부터 여섯째자리까지의 수를 정수 X로 읽어 소수 대신 이용하는 것으로 실수오차를 회피할 수 있다.

X/1000000 < K/M 인지 실수연산 없이 비교하기 위해 양변에 M * 1000000을 곱하면, X * M < K * 1000000와 같은 동치인 관계식을 얻을 수 있다. 이 식을 이용해 X를 순서대로 정렬하여 스위핑을 이용해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;

ll M;
ll arr[1000000];

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

	cin >> M;
	int N = 0;
	string s;
	while (cin >> s) {
		while ((int)s.length() < 8) s += '0';
		arr[N++] = stoll(s.substr(2, 6));
	}

	sort(arr, arr + N);

	int cnt = 0;
	ll idx = 1;
	for (int i = 0; i < N; i++) {
		if (arr[i] * M < 1000000LL * idx) cnt++;
		else {
			cout << cnt << ' ';
			cnt = 0;
			idx++;
			i--;
		}
	}

	while (idx <= M) {
		cout << cnt << ' ';
		cnt = 0;
		idx++;
	}
}