[BOJ 백준] 분수 합(1735) C++, Java

 

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

1735번: 분수 합

 

문제 설명 : 

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

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

 

입력 : 

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

출력 : 

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

 

예제 입력 : 

2 7
3 5

예제 출력 : 

31 35

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

유클리드 호제법

 

Java 코드 : 

import java.io.*;
import java.util.*;

// 분수 합 1735 
public class Main {

	static int A, B, C, D;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 1. 입력 받는다
		A = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		C = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		
		
		// 2. 연산이 가능하게 분모끼리 곱한다
		//  A       C       A*D    C*B
		//  -   +   -    =   -  +   -
		//  B       D       B*D    B*D
		//    1) 각 분자에 상대 분모를 곱함
		int boonja1 = A * D;
		int boonja2 = C * B;
		
		//    2) 분모는 B에 D를 곱해서 사용
		int boonmo = B * D;
		
		//    3) 분자를 더 해줌
		boonja1 = boonja1 + boonja2; 
		
		//    4) 최대공약수를 구함
		int gcd = getGcd(boonja1, boonmo);
	
		bw.write( (boonja1 / gcd) + " " + (boonmo / gcd) );
		
		
		bw.flush();
		bw.close();
		br.close();
	}

	
	static int getGcd(int a, int b) {
		int c;
		while (b!=0) {
			c = a%b;
			a = b;
			b = c;
		}
		return a;
	}
	
}

 

C++ 코드 : 

// 분수 합 1735 
#if 1
#pragma warning(disable:4996)
#include <cstdio>

#define MAX (30000+3)

using namespace std;

int gcd(int a, int b) {
	// a > b가 되도록 swap(a,b)
	if (b > a) {
		int tmp = b;
		b = a;
		a = tmp;
	}

	// 유클리드 호제법
	int c;
	while (b) {
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}

int A, B;			// A/B
int C, D;           // C/D

int main() {
	// 1. 입력받는다
	//freopen("input.txt", "r", stdin);
	scanf("%d %d %d %d", &A, &B, &C, &D);

	// 2. 연산이 가능하게 분모끼리 곱
	// 1) 각 분자에 상대 분모를 곱해줌
	A *= D;
	C *= B;

	// 2) 분모는 B에 D를 곱해서 사용
	B *= D;

	// 3) 분자를 더해줌    => A/B 에 분자의 합 연산완료
	A += C;

	// 4) 기약분수를 만들기위해 최대공약수로 나눠줌
	int G = gcd(A, B);


	// 3. 정답 출력
	printf("%d %d", A / G, B / G);
	
	return 0;
}
#endif