컴퓨터/백준 알고리즘

백준 알고리즘 - 1735번: 분수 합 [Java]

이상한 나그네 2023. 9. 20. 00:38

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

 

1735번: 분수 합

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

www.acmicpc.net

1. 코드

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[][] ab = new int[2][2];
		for(int i = 0; i < 2; i++) {
			for(int j = 0; j < 2; j++)
				ab[i][j] = sc.nextInt();
		}
		
		ab[0][0] *= ab[1][1];
		ab[1][0] *= ab[0][1];
		ab[0][1] *= ab[1][1];
		int[] answer = { ab[0][0] + ab[1][0], ab[0][1] };
		int GCD = gcd(Math.max(answer[0], answer[1]), Math.min(answer[0], answer[1]));
		for(int n : answer)
			System.out.print(n / GCD + " ");
	}
	
	private static int gcd(int a, int b) {
		if(b == 0) return a;
		return gcd(b, a % b);
	}
}

2. 설명

ab[0][0] *= ab[1][1];
ab[1][0] *= ab[0][1];
ab[0][1] *= ab[1][1];
int[] answer = { ab[0][0] + ab[1][0], ab[0][1] };

분수의 합을 진행합니다.

int GCD = gcd(Math.max(answer[0], answer[1]), Math.min(answer[0], answer[1]));
for(int n : answer)
    System.out.print(n / GCD + " ");

분모와 분자의 최대공약수를 gcd 함수를 통해서 도출한 뒤 나누어주면 문제는 해결됩니다.

3. 정리

  1. 유클리드 호제법을 적절히 활용하자