[BOJ][C++] 백준 20003번: 거스름돈이 싫어요

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

20003번: 거스름돈이 싫어요

 

문제

프로불편러 지수는 딱 떨어지지 않는 수는 질색이다. 거스름돈이 남는 것도 딱 질색이다. 지수가 아이템을 사려 하는데, 아이템의 가격은 다 분수로 이루어져 있다. 지금은 가령, 3/2코인을 사려고 2코인을 적립하고 결제하면 1/2코인이 남아버리는 것이다. 그래서 개발사에게 모든 아이템을 딱 떨어지게 나눌 수 있는 가격 단위를 건의하기 위해, 새로운 가격 단위는 최대 몇 코인인지를 구하려고 한다.

N개의 종류의 아이템을 딱 떨어지게 나눌 수 있는 코인 단위를 구하라. 이때 아이템과 코인은 모두 분수 형태로 나와야 한다.

입력

첫 번째 줄에는 아이템의 개수 N (1 ≤ N ≤ 50)이 주어진다.

두 번째 줄부터는 한 줄에 분자 A, 분모 B (1 ≤ A, B ≤ 40) 쌍이 주어진다. 이는 기약분수 형태가 아닐 수도 있다.

출력

새로운 코인 단위의 분자, 분모를 공백으로 구분하여 출력한다. 단, 기약분수 형태이다.

 

 

풀이

1. 각 분수들을 분모의 최소공배수로 통분

2. 분자들의 최대공약수를 구해서 답 분수 구하기

3. 답분수 약분

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> ci;

ll getGcd(ll a, ll b) {
    ll tmp;
    while(b>0) {
        tmp = a%b;
        a = b;
        b = tmp;
    }
    return a;
}

ll getLcm(ll a, ll b) {
    return a / getGcd(a, b) * b;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    int n, a, b;
    ll gcd, lcm=1;
    cin >> n;
    vector<ci> v(n);
    for(int i=0; i<n; i++) {
        cin >> a >> b;
        lcm = getLcm(b, lcm);
        v[i] = {a,b};
    }
    
    // 통분하여 다시 넣어주기
    ll boonmo = lcm;
    for(int i=0; i<n; i++)
        v[i] = {lcm / v[i].second * v[i].first, boonmo};

    
    // 분자들의 최대공약수 구해주기
    ll boonja = v[0].first;
    for(int i=1; i<n; i++)
        boonja = getGcd(boonja, v[i].first);

    
    // 약분하기
    gcd = getGcd(boonmo, boonja);
    boonja /= gcd;
    boonmo /= gcd;
    cout << boonja << " " << boonmo;
    
    return 0;
}

/*
 */