백준 1735번: 분수 합 (Java, 유클리드 호제법, 정수론)

☑️ 문제

https://www.acmicpc.net/problem/1735

✔️관련 알고리즘 개념

유클리드 호제법

☑️ 문제 분석

• 예시 입력이 2/7 + 3/5이면 두 분수를 7과 5의 곱으로 통분한다.
  • 해당 예시 입력은 35로 통분해준다.
  • 10/35 + 21/35 = 31/35이고 계산 결과가 기약분수가 아니라면
  • 분모, 분자의 최대 공약수로 나눠준다.
    • 최대 공약수를 구할 때는 유클리드 호제법에 따라 gcd함수를 구현하여 구한다.

☑️ 코드

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());

        st = new StringTokenizer(br.readLine());
        int c = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());

        // 통분해서 분수 계산하기
        a *= d;
        c *= b;

        int numerator = a + c;
        int denominator = b * d;

        int gcd = gcd(numerator, denominator);
        System.out.println(numerator / gcd + " " + denominator / gcd);
    }

    static int gcd(int a, int b) {
        if(b == 0) return a;
        else return gcd(b, a%b);
    }
}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 없음