취미로 코딩하기

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

이번에 볼 문제는 백준 27108번 문제인 Ordered Fractions이다.
문제는 아래 링크를 확인하자.

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

0/1과 1/1, 그리고 $N$ 이하의 분모를 갖는 모든 기약분수를 크기순으로 나열하는 문제이다.

이에 해당하는 기약분수의 수는 충분히 적으므로, 모든 기약분수를 벡터에 저장한 후 각 기약분수를 크기순으로 정렬해 문제를 해결할 수 있다. 각 분수가 기약분수인지 판정하는 것은 유클리드 호제법을 이용해 어렵지 않게 해낼 수 있다.

이 과정에서 분수의 대소 비교는 실수값으로 해도 좋지만 두 분모의 공배수를 두 분수에 곱해도 대소관계가 변하지 않음을 이용하면 정수의 비교로도 오차 없이 구현할 수 있다.

이 문제에서 출력해야 하는 수열의 성질을 더 깊이 알아보고 싶다면 Farey Sequence와 Stern-Brocot Tree에 대해 조사해보는 것을 추천한다.

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool comp(pair<int, int> &p1, pair<int, int> &p2) {
	return p1.first * p2.second < p2.first * p1.second;
}

int gcd(int x, int y) {
	if (y) return gcd(y, x % y);
	return x;
}

int N;
vector<pair<int, int>> vec;

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

	cin >> N;
	vec.emplace_back(make_pair(0, 1));
	vec.emplace_back(make_pair(1, 1));
	for (int n = 2; n <= N; n++) {
		for (int m = 1; m < n; m++) {
			if (gcd(n, m) > 1) continue;
			vec.emplace_back(make_pair(m, n));
		}
	}

	sort(vec.begin(), vec.end(), comp);
	cout << vec.size() << '\n';
	for (auto &p : vec) cout << p.first << '/' << p.second << '\n';
}