[백준] java 1735 분수 합

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

문제

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

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

입력

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

풀이과정

초등학교 때 배웠던 통분과 약분을 가까스로 기억해냈다.. 서로 다른 분모를 갖는 분수의 합을 구하기 위해서는 먼저, 아래의 이미지와 같은 단계로 통분을 해야한다. 통분은 서로의 분모를 곱한 뒤 분자에도 똑같이 곱해준다. 그리고 분자끼리 더해주면 된다.

그리고 출력 조건이 기약분수를 출력하는 것인데, 통분하여 더한 분자와 분모를 약분해주기만하면 된다. 약분은 아래 이미지와 같이 진행되는데, 분자와 분모의 최대 공약수를 구하여 나눠주면 된다.

[출처] 위키백과

다음은 자바를 사용한 풀이이다.

먼저 입력으로 주어진 두 개의 분수를 통분하여 서로 더한 값을 a와 b에 할당하고 유클리드 호제법을 사용하여 약분하였다.

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));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		st = new StringTokenizer(br.readLine(), " ");
		int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine(), " ");
		int c = Integer.parseInt(st.nextToken()), d = Integer.parseInt(st.nextToken());

		a *= d;
		c *= b;

		a += c;
		b *= d;

		// 유클리드 호제법
		int temp = 0, gcdA = a, gcdB = b;
		if( gcdB > gcdA ) {
			temp = gcdA;
			gcdA = gcdB;
			gcdB = temp;
		}
		while( gcdB != 0 ){
			temp = gcdA;
			gcdA = gcdB;
			gcdB = temp%gcdB;
		}
		System.out.println( (a /= gcdA) + " " + (b /= gcdA) );
	}
}