[백준] 1735번 분수 합 (C++) - Euclidean algorithm

문제

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

1735번: 분수 합

코드

#include <iostream>

using namespace std;

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

int main(){
  int a1,a2,b1,b2,result1,result2,gcdd;
  cin >> a1 >> a2 >> b1 >> b2;
  result1 = a1*b2+a2*b1;
  result2 = a2*b2;
  gcdd = gcd(result1, result2);
  cout << result1/gcdd << ' ' << result2/gcdd << '\n';
  return 0;
}

정리

유클리드 호제법을 이용해 최대공약수를 구하여 풀면 되는 문제이다. 유클리드 호제법을 이용해서  최대공약수 구하는 방법을 기억해둬야 겠다.

참조

https://kdongree.tistory.com/25