[JAVA] 백준 1735번 분수 합

문제

 

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

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

 

입력

 

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

 

출력

 

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

 

입력예제

 

2 7
3 5

 

출력예제

 

31 35

 

풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

            int a1 = scanner.nextInt();
            int a2 = scanner.nextInt();
            int b1 = scanner.nextInt();
            int b2 = scanner.nextInt();

            // 어느 숫자가 더 큰지 비교
            int min = a2 > b2 ? b2 : a2; // 작은 수
            int max = a2 > b2 ? a2 : b2; // 큰 수

            int res = 0; // 최소 공배수
            int x = 0; // 최대 공배수를 구할 때 전 값을 담아줄 변수
            for (int i = 0; i < 9999; i++) {
                x = max % min;
                max = min;
                if (x == 0) {
                    res = (a2 * b2) / min;
                    break;
                }
                min = x;

            }

            // 분수합 계산 분자
        int y = a1 * (res/a2) + b1 * (res/b2);

        min = y > res ? res : y; // 작은 수
        max = y > res ? y : res; // 큰 수

        // 약분시키기
        for (int i = 0; i < 9999; i++) {
            x = max % min;
            max = min;
            if (x == 0) {
                bw.write(y/min + " " + res/min);
                break;
            }
            min = x;

        }




        bw.flush();
        bw.close();
    }
}

 

 

유클리드 호제법을 알면 쉽게 풀 수 있다.

 

최소공배수를 구하는 방법은

최소공배수 = (A * B) / 최대공약수 이다.

 

 

 

 

 

1735번: 분수 합