백준 1735번 분수 합

< 백준 1735번 분수 합 - 마포 코딩박 >

사용한 알고리즘: 수학


 두 분수가 주어질때 분수의 합을 기약분수로 나타내는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 11~15)
 a/b + c/d = (a*d + c*b) / b*d 입니다.

(2) (코드 5~8)
 gcd 를 구현하는 함수를 만들어 주었습니다.

(3) (코드 16~17)
 G=gcd( (a*d + c*b), b*d ) 라고 하면 기약분수는 ((a*d + c*b)/G) / (b*d/G) 입니다.

	#include <bits/stdc++.h>
	using namespace std;
	int a, b, c, d;
	int GCD(int x, int y){
	if(y==0) return x;
	return GCD(y, x%y);
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> a >> b >> c >> d;
	a *= d;
	c *= b;
	a += c;
	b *= d;
	int G = GCD(a,b);
	cout << a/G << ' ' << b/G << '\n';
	return 0;
	}

view raw BOJ 1735.cpp hosted with ❤ by GitHub