[백준][1735번][유클리드 호제법] 분수 합

분수 합

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

<코드>

#include <stdio.h>
 
int gcd(int n1, int n2){
    if (n2%n1 == 0){
        return n1;
    }
    else
        gcd(n2%n1, n1);
}
 
int main(void){
    int a_u, a_d;
    int b_u, b_d;
    int gcd_num;
    int result_u, result_d;
 
    scanf("%d %d", &a_u, &a_d);
    scanf("%d %d", &b_u, &b_d);
 
    gcd_num = gcd(a_d, b_d);
 
    result_d = a_d*b_d / gcd_num;
    result_u = result_d / a_d *a_u + result_d / b_d*b_u;
 
    gcd_num = gcd(result_d, result_u);
 
 
 
    printf("%d %d\n", result_u/gcd_num, result_d/gcd_num);
 
 
 
    return 0;
}

<문제 푼 방법>

 1. 처음 통분을 해야하기 때문에 유클리드 호제법을 사용해서 최대 공약수를 구한다. 

 유클리드 호제법

최대 공약수를 구하는 알고리즘이다 A와 B의 최대공약수를 구한다고 예를 든다면 A = XB + R 가 된다.

위 식을 다시 B = X'R+R' 이런 식으로 계속 나누어간다. 이 때 나머지가 0이 될때의 제수가 최대 공약수가 된다.

왜 그런가?? -> 왜냐함 A 와 B 와 R 의 최대 공약수는 같다는 이론이다. 

그렇다면 A= mk , B=nk (m,n 은 서로수) 라고하면 R = (mk-Xnk) -> K(m-Xn) 즉 m-Xn, n은 서로소 일 수 밖에없다. 

즉 A 와 B 와 R의 최대공약수는 K 이다.

 2. 그 후 통분할 분자들을 통분하여 더한다. 

 3. 다 더한 값이 기약분수가 아닐 수 있으니 분모와 분자를 유클리드 호제법으로 최대공약수를 구한다.

 4. 최대공약수 값을 나눔으로써 기약 분수를 만들어 준다.