[BOJ알고리즘, C++]#1735_분수 합, 유클리드 호제법, 최대 공약수, 최소 공배수, gcd, lcm

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. 유클리드 호제법

https://webddevys.tistory.com/162

[BOJ알고리즘, C++]#2609_최대 공약수와 최소 공배수, 유클리드 호제법

int gcd(int a, int b)
{
    int c = a%b;
    while(c != 0)
    {
    	a = b;
        b = c;
        c = a%b;
    }
    return b;
}

int lcm(int a, int b)
{
    return (a * b)/ gcd(a, b);
}

유클리드 호제법은 2개의 자연수의 최대공약수(gcd)를 구하는 알고리즘의 하나입니다. A와 B를 나눈 나머지 값을 R이라고 한다면, A와 B의 최대 공약수는 B와 R의 최대 공약수와 같습니다! 이 성질을 이용하여, B(혹은 Determinant)를 이전의 나머지 값으로 나누는 작업을 반복합니다. 최종적으로, 나머지 값이 0이 되었을 때, "마지막 B" 값이 A와 B의 최대 공약수가 되는 것입니다.

 

2. lcm(분모1, 분모 2)/분모 1, lcm(분모 1, 분모 2)/분모 2

1. 먼저, 두 분모의 lcm값을 찾아줍니다.
2. 그리고, 각 분자에 lcm(분모 1, 분모2)/분모1, lcm(분모1, 분모 2)/분모 2해줍니다.
3. 마지막으로, (분자/gcd(분자, 분모))/(분모/gcd(분자, 분모))로 표현해 준다.

 

---

 

#3. 코드

/*
    @문제: 주어진 두 분수의 합을 기약 분수의 형태로 나타내는 문제
    @설명
        1. 유클리드 호제법: 최대 공약수
        2. 먼저, 두 분수의 분모의 lcm(최소 공배수)를 찾아줍니다.
        3. 그리고, 두 분수의 분자에 각각 lcm(분모1, 분모2)/분모1, lcm(분모1, 분모2)/분모2를 곱해주고, 이 둘의 합을 구합니다.
        2. 마지막으로,  (분자/gcd(분자,분모))/(분모/gcd(분자,분모))로 표현해준다.
*/

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

int A, B;

int gcd(int a, int b)
{
    int c = a%b;

    while(c != 0)
    {
        a = b;
        b = c;
        c = a%b;
    }

    return b;
}

int lcm(int a, int b)
{
    return (a*b)/gcd(a,b);
}

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

    vector<pair<int,int>> v;
    for(int i=0; i<2; ++i)
    {
        cin >> A >> B;

        v.push_back({A,B});
    }

    // 분자 = 분자 * (LCM/분모)
    int denominator = lcm(v[0].second, v[1].second);

    int numerator = 0;
    for(int i=0; i<2; ++i)
    {
        numerator += v[i].first * (denominator/v[i].second);
    }

    // (분자/분모와 분자의 최대 공약수) / (분모/분모와 분자의 최대 공약수)
    int GCD = gcd(numerator, denominator);
    cout << numerator/GCD << ' ' << denominator/GCD;

    return 0;
}

 

---