[BaekJoon] 1735 분수 합

1.  문제 링크

2.  문제

요약

• 주어진 두 분수의 합을 기약분수로 구한 후, 분자와 분모를 출력하는 문제입니다.
• 입력: 첫 번째 줄과 두 번째 줄에는 분자 분모가 각각 주어집니다.
• 출력: 두 분수의 합을 기약분수로 구한 후, 분자와 분모를 출력합니다.

3.  소스코드

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 int gcd(int numerator, int denominator) {
		int min, max;
		int num;
		if(numerator > denominator) {
			min = denominator;
			max = numerator;
		} else {
			min = numerator;
			max = denominator;
		}
		while(min != 0) {
			num = max % min;
			max = min;
			min = num;
		}
		return max;
	}
	
	public int[] getSimpleFraction(String input1, String input2) {
		int[] result = new int[2];
		StringTokenizer st = new StringTokenizer(input1);
		int numerator1 = Integer.parseInt(st.nextToken());
		int denominator1 = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(input2);
		int numerator2 = Integer.parseInt(st.nextToken());
		int denominator2 = Integer.parseInt(st.nextToken());
		int numerator = numerator1 * denominator2 + numerator2 * denominator1;
		int denominator = denominator1 * denominator2;
		int gcd = gcd(numerator, denominator);
		result[0] = numerator / gcd;
		result[1] = denominator / gcd;
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String input1 = br.readLine();
		String input2 = br.readLine();
		br.close();
		Main m = new Main();
		int[] result = m.getSimpleFraction(input1, input2);
		for(int i = 0; i < 2; i++) {
			bw.write(result[i] + " ");
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

• 분모를 같은 수로 맞춰줘야 하는데, 최소공배수를 찾아서 분모를 맞추는 대신, 최소공배수를 찾는 시간을 줄이기 위해 두 분모를 곱하여 분모를 맞춰줍니다.
• 분자는 각자 서로의 분모를 곱하여 더해 분자를 구합니다.
• 기약분수는 분모와 분자의 최대 공약수가 1이어야 하기 때문에 구한 분자와 분모에 대해 최대 공약수를 찾아 분자와 분모에 각각 최대 공약수로 나눠줍니다.
• 최대 공약수는 유클리드 알고리즘을 이용하여 구합니다.
• 임의의 두 자연수 a, b가 주어졌을 때, 둘 중 큰 값이 a라고 한다면 a % b를 한 값을 n이라고 가정합니다.
• n이 0일 때, b가 최대 공약수가 됩니다.
• 만약 n이 0이 아니라면 a에 b의 값을 넣어주고, b에 n을 넣어준 후 다시 a % b를 하여 이 값을 n으로 하고 위 과정을 반복합니다.
• 이렇게 구한 기약분수의 분자와 분모를 출력합니다.