문제 출처

단계별로 풀어보기 > 약수와 소수와 배수 2 > 분수 합
https://www.acmicpc.net/problem/1735

문제 설명

2줄에 거처 각각 분자 분모 가 주어질 때, 다음 두 수의 기약 분수를 분자 분모 형태로 출력하라.

접근 방법

최대공약수를 구하여 각 분자와 분모를 최대공약수를 나눠서 출력한다.

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

public class 분수_합 {
    public static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int m = (a * d) + (b * c); //분자
        int n = b * d; //분모

        int k = 0;
        if(m > n) k = gcd(m, n);
        else k = gcd(n, m);

        StringBuilder sb = new StringBuilder();
        sb.append(m/k).append(" ").append(n/k);

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

유클리드 호제법을 자바 코드로는 알고 있었지만, 실제로 이번에 증명을 해본건 처음이였다. 이해할꺼 같으면서도, 뭔가 살짝 이해가 안되는 느낌이다.

그래도 실제로 증명 과정을 따라가보니 어떻게 흘러가는지 이해는 된다.

증명은 문제푼 흔적 2번째 사진

문제푼 흔적