정올 1985번: 분수 정렬

문제

문제 바로가기> 정올 1985번: 분수 정렬

JUNGOL

 

풀이 1

* 1/2과 2/4처럼 값이 겹치는 경우 분모가 작은 1/2을 선택 (분모가 작으면 분자도 작다)

 

조합 가능한 모든 분수를 생성해주고, 분수값(오름차순) 과 분모값(오름차순)을 기준으로 정렬해준다.

만약 분수값이 이전 분수값과 같다면 continue 해주면 된다.

분모의 범위를 2부터, 분자의 범위를 1부터 한 것은 0과 1이 되는 값은 어차피 0/1과 1/1이 출력될 것이기 때문이다.

100000 을 곱해준 후 나눈 값을 저장한 것은 소수가 아닌 정수 형태로 저장하기 위함이다. 1.0을 곱해주고 double로 저장해서 계산해도 된다.

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

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

void input(){
    cin >> N;
}

void solution(){
    for(int parent=2; parent<=N; parent++){ // 분모
        for(int child=1; child<parent; child++){ // 분자
            fraction.push_back({child*100000/parent, {child, parent}});
        }
    }
    sort(fraction.begin(), fraction.end());
}

void output(){
    cout << "0/1\n";
    for(int i=0; i<fraction.size(); i++){
        if(i!=0 && fraction[i].first == fraction[i-1].first) continue;
        cout << fraction[i].second.first << "/" << fraction[i].second.second << "\n";
    }
    cout << "1/1\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution();
    output();
}

 

풀이 2

정렬을 사용하지 않고, 다음과 같이 index를 사용하여 푸는 방법도 있다.

#include<iostream>
#define MAX 100000
using namespace std;

int N;
int child[MAX], parent[MAX];

void input(){
    cin >> N;
}

void solution(){
    for(int par=2; par<=N; par++){ // 분모
        for(int chi=1; chi<par; chi++){ // 분자
            int idx = chi*MAX/par;
            if(parent[idx]) continue;
            child[idx] = chi;
            parent[idx] = par;
        }
    }

}

void output(){
    cout << "0/1\n";
    for(int i=0; i<MAX; i++){
        if(parent[i] == 0) continue;
        cout << child[i] << "/" << parent[i] << "\n";
    }
    cout << "1/1\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution();
    output();
}