[백준][c++] 1735번: 분수 합

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

문제 해석

• 최대공약수를 이용해 기약분수 구하기

알고리즘 분류

• 수학
• 정수론
• 유클리드 호제법

풀이

• 최대공약수를 구한다
• 두 분수의 합의 분모와 분자를 최대공약수로 나눠 기약분수로 만든다

코드

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

int GCD(int a, int b) {
    while (b != 0) {
        int temp = a;
        a = b;
        b = temp % a;
    }
    return a;
}

int main() { 
    int a,b,c,d;
    cin >> a >> b >> c >> d;

    int numerator = a * d + b * c;
    int dominator = b * d;

    int gcd = GCD(numerator, dominator);
    cout << numerator/gcd <<" "<< dominator/gcd;
    
    return 0;
}