[백준 문제 풀기] 1735번: 분수 합 (재귀?, 자바)

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

 

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

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

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

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

 

예제 입력, 출력

	예제 입력	예제 출력
1	2 7 3 5	31 35

 

사용 알고리즘

GCD 구할려고 재귀를 쓰긴 했음

코드 (자바)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 분수 합 : https://www.acmicpc.net/problem/1735

public class Main {
	
	// 최대공약수를 구하는 메소드
	static int gdc (int a, int b) {
		if (b==0) {
			return a;
		}
		
		return gdc (b, a%b);
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine().trim());
		
		int a1 = Integer.parseInt(st.nextToken());	// 첫번째 숫자의 분자
		int a2 = Integer.parseInt(st.nextToken());	// 첫번째 숫자의 분모
		
		st = new StringTokenizer(br.readLine().trim());
		int b1 = Integer.parseInt(st.nextToken());	// 두번째 숫자의 분자
		int b2 = Integer.parseInt(st.nextToken());	// 두번째 숫자의 분모
		
		int ans1 = 0;	// 답의 분자
		int ans2 = 0;	// 답의 분모
		
		// 로직 시작
		int temp1 = 0;	// 연산에 쓸 임시 분자
		int temp2 = 0;	// 연산에 쓸 임시 분모
		
		temp2 = a2*b2;
		temp1 = a1*b2 + b1*a2;
		
		ans1 = temp1 / gdc (temp1, temp2);
		ans2 = temp2 / gdc (temp1, temp2);
		
		System.out.println(ans1 + " " + ans2);
		
	}
}

/* [인터돌™] 공부 해보자!! 열심히~~~ http://globalhost.tistory.com */