[JAVA/유클리드호제] 분수 합_1735

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

1735번: 분수 합

분수 합 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

22129

10330

8855

48.175%

문제

분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자.

두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다.

입력

첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다.

출력

첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다.

예제 입력 1 복사

2 7
3 5

예제 출력 1 복사

31 35

 

 

 

package baekjoon;

import java.util.Scanner;

public class Main {
	
	
    public static void main(String[] args) {
    	
    	Scanner s = new Scanner(System.in);
    	
    	long fstX = s.nextLong(); // 첫째 수의 분자
    	long fstY = s.nextLong(); // 첫째 수의 분모
    	
    	long sndX = s.nextLong(); // 둘째 수의 분자
    	long sndY = s.nextLong(); // 둘째 수의 분모
    	
    	// 우선 두 분수를 기약분수로 만들고 시작한다.
    	long gcdFst = gcd(fstX, fstY);
    	long gcdSnd = gcd(sndX, sndY);
    	
    	fstX /= gcdFst;
    	fstY /= gcdFst;
    	sndX /= gcdSnd;
    	sndY /= gcdSnd;
    	
    	// 이제 두 분모의 최소공배수를 구한다.
    	long lcmY = lcm(fstY, sndY);
    	
    	// 분모의 최소공배수 결과에 따라 분자도 곱셈을 수행한다.
    	fstX *= (lcmY/fstY);
    	sndX *= (lcmY/sndY);
    	long answerX = fstX + sndX;
    	
    	// 한 번 더 기약분수로 만들기
    	long finalGcdY = gcd(answerX, lcmY);
    	answerX /= finalGcdY;
    	lcmY /= finalGcdY;

    	System.out.println(answerX+" "+lcmY);
    	
    }
    
    // 유클리드 호제법 : 작은 수가 0이 될 때까지 나머지를 구했을 때 나온 값이 최대공약수
    static long gcd(long a, long b) {
    	
    	long bigNum = a;
    	long smlNum = b;
    	
    	if(a < b) {
    		bigNum = b;
    		smlNum = a;
    	}
    	
    	while(smlNum > 0) {
    		long mod = bigNum % smlNum;
    		bigNum = smlNum;
    		smlNum = mod;
    	}
    	
    	return bigNum;
    }
    
    // 최소공배수 구하기 : a와 b의 최소공배수는 a*b/(최소공배수) 이다.
    static long lcm(long a, long b) {
    	return a*b/gcd(a, b);
    }
}