BOJ 24146 : 分数 (Fraction)

• 문제 링크 : boj.kr/24146
• 난이도 : G3
• 태그 : 우선순위 큐, 정수론

Baekjoon Online Judge

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

struct compare{
    bool operator()(pii &a, pii &b) {
        return a.first*b.second > b.first*a.second;
    }
};

ll gcd(ll a, ll b)
{
    if (!b) return a;
    return gcd(b, a % b);
}

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

    int m, k;
    cin >> m >> k;
    priority_queue<pii, vector<pii>, compare> _pq;
    for(int i = 2; i <= m; i++) {
        _pq.push({1, i});
    }

    int idx = 1;
    while(!_pq.empty() && idx <= k) {
        pii curr = _pq.top(); _pq.pop();
        if(curr.first + 1 < curr.second) _pq.push({curr.first+1, curr.second});
        if(gcd(curr.first, curr.second) != 1) {
            continue;
        }
        if(idx == k) {
            cout << curr.first << " " << curr.second;
            return 0;
        }
        idx++;
    }

    cout << -1;
    return 0;
}

---

풀이

dong_gas의 글을 보고 풀게 되었다.

a/b < (a+1)/b는 당연하다. 이는 분수들을 작은 순서대로 확인할 때 아직 a/b를 확인하지 않았다면 (a+1)/b는 고려할 필요도 없다는 것을 의미한다.

따라서 동시에 봐야할 분수들의 수는 최대 M개이다.

동시에 보고 있는 분수들 중 가장 작은 분수를 골라내기 위해 우선순위 큐를 사용한다.

이때 기약분수가 아닌 분수들도 보게 될 텐데, 분자와 분모의 gcd를 확인하여 1이 아니라면 그대로 넘긴다.

 

처음 M개의 분수를 우선순위 큐에 넣는데에 O(MlogM), M개의 분수들 중 가장 작은 기약분수를 K번 확인하는데에 O(KlogMlogM)이므로 총 시간복잡도는 O((M+KlogM)logM)이다.