본문 바로가기

Programming/BOJ

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)




참고



태그