[BOJ]1735번: 분수 합

1735번: 분수 합

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

이 문제는 심심풀이로 올려본다.

중학교? 이상이면 다 풀 수 있는 문제다.

근데 여기서 기약 분수로 해줘야 하므로, 분모에 있는 값과 분자에 있는 값의 최대 공약수를 구해서 그 수로 나눠주면 기약분수가 된다.

최대 공약수를 구하는 방법은 유클리드 아저씨가 만드신 유클리드 호제법이라는 게 있는데 굉장히 좋당...

유클리드 호제법(위키피디아): https://goo.gl/gsRPhY

링크를 남겨둘 테니, 한번 쭉 읽어보길 바랍니다.

#include <stdio.h>
 
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
 
int main(void)
{
    int a,b,c,d;
    int f1, f2, f3;
    scanf("%d %d %d %d", &a, &b, &c, &d);
    
    f1 = b * d;
    f2 = a * d + c * b;
    f3 = gcd(f1, f2);
    f1 /= f3;
    f2 /= f3;
 
    printf("%d %d", f2, f1);
 
    return 0;
}