[Java] 백준 1735번: 분수 합

문제 url:
분수 합

문제:

🤔 문제 알아보기

공백으로 구분 된 A, B를 받는데, 여기서 A는 분자 B는 분모로 지칭한다.
또한 이를 두 개를 받아, 두 분수끼리 더한 값을 구한 다음 기약분수로 만드는 것이 문제이다.

기약분수란?
기약분수는 분모와 분자의 공약수가 1뿐인 분수를 말해요. 기약분수는 분모와 분자가 더는 나눠지지 않는 분수

여기서 공약수가 1인 분수라고 하는데, 그렇다면! 분자와 분모의 최대공약수를 구해서 이를 나누면 공약수가 1인 분수가 되지 않겠는가?

바로 코드로 풀어보자

🐱‍👤 실제 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int A2 = Integer.parseInt(st2.nextToken());
        int B2 = Integer.parseInt(st2.nextToken());

        int num = A * B2 + A2 * B;  // 분자(numerator)
        int den = B * B2;           // 분모(denominator)

        int gcd_value = gcd(num, den);

        System.out.println(num / gcd_value + " " + den / gcd_value);


    }

    static int gcd(int num, int den) {
        if(den == 0) {
            return num;
        }

        return gcd(den, num % den);
    }
}

gcd(greatest common divisor, 최대공약수)를 구할 수 있으면 쉽게 풀 수 있다.
해당 문제는 최대공약수를 구하는 유클리드 호제법을 사용해서 풀 수 있다.

아래의 링크를 통해 알아보자
유클리드 호제법이란?