[BaekJoon] 1735번 분수 합 문제풀이 (Success)

1735번: 분수 합

 

☕Language: Java

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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 st1 = new StringTokenizer(br.readLine(), " ");
        double top1 = Integer.parseInt(st1.nextToken());
        double bottom1 = Integer.parseInt(st1.nextToken());
 
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
        double top2 = Integer.parseInt(st2.nextToken());
        double bottom2 = Integer.parseInt(st2.nextToken());
 
        double top = 1;
        double bottom = 0;
        Loop: for (double i = 1; i <= bottom2; i++) {
            for (double j = 1; j <= bottom1; j++) {
                if (bottom1 * i == bottom2 * j) {
                    bottom = bottom1 * i;
                    top = top2 * j + top1 * i;
                    break Loop;
                }
            }
        }
 
        for (double k = 2; k <= (top >= bottom ? top : bottom); k++) {
            if (top % k == 0 && bottom % k == 0) {
                top /= k;
                bottom /= k;
            }
        }
 
        bw.write((int)top + " " + (int)bottom);
 
        bw.flush();
        bw.close();
    }
 
}
 

🚨 입력값이 30,000일 때 top, bottom값을 구하기까지의 2중 for문에서 시간 초과 발생

    - 시간 복잡도: O(n^2)

 

😮 이 외의 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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 st1 = new StringTokenizer(br.readLine(), " ");
        int top1 = Integer.parseInt(st1.nextToken());
        int bottom1 = Integer.parseInt(st1.nextToken());
 
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
        int top2 = Integer.parseInt(st2.nextToken());
        int bottom2 = Integer.parseInt(st2.nextToken());
 
        int top = top1 * bottom2 + top2 * bottom1;
        int bottom = bottom1 * bottom2;
 
        int gdc = getGCD(top, bottom);
 
        bw.write((top/gdc) + " " + (bottom/gdc));
 
        bw.flush();
        bw.close();
    }
    
    public static int getGCD(int p, int q) {
        return q == 0 ? p : getGCD(q, p%q);
    }
 
}
 

- 유클리드 호제법

    -  2개의 자연수의 최대공약수를 구하는 알고리즘

    - 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같음
    - p를 q로 나누어 떨어지면 q가 최대 공약수, 나누어 떨이지지 않으면 p를 q로 나눈 나머지에 대해서 getGCD 수행

    - 예시: 36, 27

        - 36은 27로 나누어 떨어지지 않으므로 27과 9에 대해서 getGCD 실행

        - 27은 9로 나누어 떨어지므로 9가 36과 27의 최대 공약수

 

 

 

🔗 소스 코드
HJ0216/TIL/BOJ

 

📚 참고 자료

[Algorithm] 유클리드 호제법(최대공약수 구하기) 공부