[백준] 1735 분수 합

1735번: 분수 합

 

www.acmicpc.net

풀이

최대 공약수와 최소 공배수를 이용해서 해결하는 문제이다. 분수 덧셈을 하기 위해서 분모들의 최소 공배수를 알아야한다. 최소 공배수를 구하고 나면 분자에 어떤 수를 곱해야하는지를 알 수 있으므로 덧셈 결과를 구할 수 있다. 덧셈이 끝난 뒤 분모와 분자의 최소 공배수를 구해서 기약 분수로 만들어주면 된다.

코드

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

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

    int a1, a2, b1, b2;
    cin >> a1 >> b1;
    cin >> a2 >> b2;
    // 분모들의 최소공배수 계산
    int lcm = b1 * b2 / gcd(b1, b2);
    int child1 = a1 * (lcm / b1);
    int child2 = a2 * (lcm / b2);
    int child = child1 + child2;
    // 덧셈 결과 분모와 분자의 최소 공배수 계산
    int g = gcd(child, lcm);
    // 최소 공배수가 1이면 이미 기약분수이므로 답 출력
    if (g == 1) cout << child << ' ' << lcm << '\n';
    else cout << child / g << ' ' << lcm / g << '\n';
    return 0;
}