[자바] 백준 1735번 분수 합

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

 

두 개의 분수를 입력한 다음 분수의 합을 구하는 문제였다. 여기서 특징은 기약분수를 구해야한다는 것이었는데! 어떻게 구현해야될지 고민하다가 max랑 min을 사용하여 분자와 분모 중 더 큰 수까지 나눠가면서 약수를 가진다면 나눠서 기약분수로 만들 수 있도록 구현하였다. 근데 풀고 보니 풀이 자체가 틀린 건 아니지만 너무 요상해서 다른 문제 풀이 방법을 좀 찾아봤다.

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

public class Main {

    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 s = (a*d) + (b*c);
        int p = (b*d);

        int max = 0;
        int min = 0;
        if (s > p) {
            max = s;
            min = p;
        }
        else{
            max = p;
            min = s;
        }
        int i = 2;
        while(i <= min){
            if(max % i == 0 && min % i == 0){
                min /= i;
                max /= i;
                i = 2;
            }
            else{
                i++;
            }
        }
        if (s > p) {
            s = max;
            p = min;
        }
        else{
            p = max;
            s = min;
        }

        bw.write(String.valueOf(s) + " " + String.valueOf(p));
        bw.flush();
        bw.close();
    }
}

 

원래 이 문제의 의도는 유클리드 호제법을 사용하는 것이었다..!

 

유클리드 호제법 : 최대 공약수를 구하는 알고리즘

 public static int gcd(int p, int q)
 {
	if (q == 0) return p;
	return gcd(q, p % q);
 }

 

이 알고리즘을 통해 최대 공약수를 손쉽게 구할 수 있다. 유클리드 호제법을 사용해 문제를 다시 풀어보자

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

public class Main {

    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 s = (a*d) + (b*c);
        int p = (b*d);

        int gcd = gcd(s, p);
        s /= gcd;
        p /= gcd;

        bw.write(String.valueOf(s) + " " + String.valueOf(p));
        bw.flush();
        bw.close();
    }

    public static int gcd(int p, int q){
        if(q == 0) return p;
        return gcd(q, p % q);

        // ex. 4, 8 넣으면 gcd(4, 0) -> 4
    }
}

 

p>q 라고 가정할 때, p % q = r 이라고 하면, p와 q의 최대 공약수는 q와 r의 최대 공약수와 같다. 이러한 공식을 따라서 계속 나머지를 구하는 과정을 반복하다가 나머지가 0이 되는 순간 나눠지는 수가 p와 q의 최대 공약수이다. 생각하면 이해가 되는데 또 생각하긴 어려우니까 일단 외워보자 ^^

 

훨씬 간결하고, 시간 복잡도도 엄청 줄였다.