(C++) 백준 1735번 분수 합

1. 링크

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

2. 풀이

• 유클리드 호제법을 이용한 최대공약수 구하는 방법을 기억하자.

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

나는 무식하게 풀었는데... 다른 풀이 보니 먼저 분수 계산 후 이를 최대공약수로 나눠주면 된다. 🥺

#include <iostream>
using namespace std;
int gcd(int a,int b)  { return b==0 ? a : gcd(b,a%b); }
int lcm(int a, int b)  {return a*b/gcd(a,b);}

int main(){

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

    while(gcd(a,b)!=1){
        int tmp = gcd(a,b);
        a/=tmp; b/=tmp;
    }
    while(gcd(c,d)!=1){
        int tmp = gcd(c,d);
        c/=tmp; d/=tmp;
    }

    int y = lcm(b,d);
    int x = a*(y/b) + c*(y/d);

    while(gcd(x,y)!=1){
        int tmp = gcd(x,y);
        x/=tmp; y/=tmp;
    }

    cout<<x<<" "<<y;

}