BOJ 1735 · 분수 합

알고리즘 분류 : 수학  

분수의 합은 유클리드 호제법을 이용하여 간단히 구현할 수 있다. 자세한 내용은 이곳을 참조.

• 먼저 두 분수를 더한다.
• 분수1 = 분자1/분모1, 분수2 = 분자2/분모2 라고 할 때, 분수 합 = (분자1*분모2 + 분자2*분모1)/(분모1*분모2)
• 합한 분수에 대한 기약 분수를 구한다.
• 분자와 분모의 GCD를 구한 후, 분자 분모에 각각 나눈다.

---

C++ 소스코드

#include <cstdio>

int gcd(int x, int y) {
    while (y != 0) {
        int r = x%y;
        x = y;
        y = r;
    }
    return x;
}
 
int main() {
    int n1, d1, n2, d2;
    scanf("%d %d %d %d", &n1, &d1, &n2, &d2);
    int n = n1*d2 + n2*d1;
    int d = d1*d2;
    int g = gcd(n, d);
    printf("%d %d\n", n/g, d/g);
    return 0;
}

---

Python 3 소스코드

def gcd(x, y):
    while y is not 0:
        r = x%y
        x = y
        y = r
    return x


n1, d1 = map(int, input().split())
n2, d2 = map(int, input().split())
n = n1*d2 + n2*d1
d = d1*d2
g = gcd(n, d)
print(n//g, d//g)

---

참고

• 백준 온라인 저지 : BOJ 1735
• 위키피디아 : 분수
• 위키피디아 : 기약분수