[백준][1735] 분수 합

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	10540	4729	3948	45.806%

문제

분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자.

두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다.

입력

첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다.

출력

첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다.

예제 입력

2 7
3 5

예제 출력

31 35

소스

package bj;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class bj1735 {

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub

        System.setIn(new FileInputStream("/Users/projooni/sample_input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = 1;
        for (int tc = 1; tc <= T; tc++) {

            StringTokenizer st = new StringTokenizer(br.readLine());
            int a1 = Integer.parseInt(st.nextToken());
            int b1 = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int a2 = Integer.parseInt(st.nextToken());
            int b2 = Integer.parseInt(st.nextToken());

            int a3 = a1 * b2 + a2 * b1;
            int b3 = b1 * b2;

            int gcd = getGCD(a3, b3);

            bw.flush();
            bw.write((a3 / gcd) + " " + (b3 / gcd));
        }
        bw.close();

    }

    public static int getGCD(int p, int q) {
        if(q == 0) {
            return p;
        }
        return getGCD(q, p%q);
    }

}

풀이

1. 2개의 분수를 일단 합친다. 분모는 그냥 곱하고, 분자도 이에 맞게 계산한다.
2. 유클리드 호제법으로 최대공약수를 구한다.
3. 1번의 결과에 최대공약수로 분자,분모를 각각 나누면 기약분수가 된다.

유클리드 호제법

1. 두 수 a,b가 있고, 두 수의 최대공약수를 구하고자 한다.
2. a를 b로 나눈다. 나머지 r이 나온다.
3. 나머지 r이 0이라면 b가 최대공약수이다. 그렇지않다면 이번에는 b를 r로 나눈다.
4. 3번에서 b를 r로 나눈 나머지가 0이면 r(나눈값)이 최대공약수이다. 그렇지 않다면 2~3번을 반복한다. (소스는 위의 정답 코드를 참고한다)

자세한 설명은 아래 링크를 참조하자
유클리드 호제법

최소공배수 구하기

1. 최대공약수 * 최소공배수 = a * b 이므로, 최대공약수를 구하면 최소공배수도 자연스럽게 구할 수 있다.