[BOJ 27258 // C++] Дроби

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

 

이번에 볼 문제는 백준 27258번 문제인 Дроби이다.
문제는 아래 링크를 확인하자.

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

27258번: Дроби

분모가 n 이하인 모든 분수에 대하여 1/p와 1/q 사이에 있는 모든 기약분수를 찾는 것은 모든 가능한 분모와 분자의 쌍에 대해 조사(브루트포스)하는 것으로 해낼 수 있다.

 

이와 같이 얻은 기약분수들을 크기순으로 정렬해 문제를 해결하자. 기약분수를 두 정수의 순서쌍으로 저장하고, a/b < c/d의 대소관계식을 ad < bc와 같은 정수의 연산으로 구현하면 오차에 구애받지 않고 문제를 해결할 수 있다.

 

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

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

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

int N, P, Q;
vector<pair<int, int>> fracs;

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

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

	cin >> N >> P >> Q;
	for (int n = 1; n <= N; n++) {
		for (int m = 1; m <= N; m++) {
			if (gcd(n, m) == 1 && n < m * P && m * Q < n) fracs.emplace_back(make_pair(n, m));
		}
	}

	sort(fracs.begin(), fracs.end(), comp);

	for (auto& p : fracs) cout << p.second << '/' << p.first << '\n';
}