[백준][C++] 1735: 분수 합

문제

풀이

유클리드 호제법

 

간단한 유클리드 호제법 문제이다. 아래는 a, b의 최대공약수를 반환하는 유클리드 호제법 함수이다.

int gcd(int a, int b)
{
    if (a < b)
    {
        swap(a, b);
    }
    
    int temp;
    while (b != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}

 

문제에서 주어진 분수를 먼저 통분하여 합을 계산한다. 합한 분자와 분모의 최대공약수를 구하여 각각에 나누면 기약 분수가 된다.

코드

#include <iostream>

using namespace std;

int gcd(int a, int b)
{
    if (a < b)
    {
        swap(a, b);
    }
    
    int temp;
    while (b != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}

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

    int a, b;
    int c, d;
    cin >> a >> b >> c >> d;

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

    int divisor = gcd(numerator, denominator);

    cout << numerator / divisor << " " << denominator / divisor;

    return 0;
}