백준 1735번 : 분수 합

---

이번 문제는 초등수학에서 배웠던 말 그대로 분수의 합을 구하는 문제이다. 다만, 기본적으로 더 이상 약분되지 않는 기약분수여야한다.

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

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

        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 resultA = (a1 * b2) + (a2 * b1);
        int resultB = b1 * b2;

        int gcd = gcd(resultA, resultB);
        System.out.println(resultA/gcd + " " + resultB/gcd);
    }
    public static int gcd(int x, int y) {
        while (y == 0) {
            return x;
        }
        return gcd(y, x%y);
    }
}

솔직히 말하면 정말 간단한 문제다.
수식을 조금만 생각하면 초등수학이 생각나지 않아도 금방 접근할 수 있다.

분수의 합을 구하는 방법은 크게 어렵지 않으니 설명할 게 없다.
그런데, 주의해야할 것이 기약분수라는 점이다.

약분이 더 이상 이루어지지 않도록 하는 것은 분수 계산법의 기본이긴한데,
이를 알고리즘으로 어떻게 표현할지가 고민되었다.

그래서 기약분수에 대해 찾아보다가 알게 된 것이 이 약분을 할 때의 공통인수가 최대공약수라는 것이다.
솔직히 말해 부끄럽지만 지금까지 수학을 놓고 산 시간이 길어서 전혀 기억해내지 못 했었다.

아무튼 이 문제에서 가장 조심해야할 것은 기약분수로 표현하는 것이었는데,
이로써 문제를 거의 다 풀었다고 할 수 있다.

이번 카테고리에 들어서서 가장 많이 나오는 유클리드 호제법을 사용한다면
최대공약수 정도는 쉽게 구할 수 있다.

public static int gcd(int x, int y) {
     if (y == 0) {
         return x;
     }
     return gcd(y, x%y);
}

재귀로 작성한 유클리드 호제법이다.
이 호제법으로 계산된 최대공약수를 사용해 각각 분자, 분모를 나누어주면 그대로 기약분수가 된다.

---

이 문제가 실버3의 난이도라는 게 조금 이상하다고 생각하는데,
아마 유클리드 호제법이라는 특정 공식을 알고 있어야 쉽게 접근할 수 있는 문제라 그런 것 같다.
솔직히 이 다음에 나오는 가로수 문제가 개인적으로 더 어려웠다.