[백준] 4587: 이집트 분수

문제 링크

https://www.acmicpc.net/problem/4587

접근 방식 / 풀이

어떤 분수에서 뺄 수 있는 가장 큰 단위 분수는 무엇일까?

이 질문의 답은, 분수의 값을 직접 나눠보면 더 빠르게 알 수 있다.

분수는 위 식과 같이 나타낼 수 있다.
만약 분모를 분자로 나눈 값이 정수라면, $\frac{b}{a}$ 은 단위 분수의 분모가 될 수 있다.
정수가 아닌 실수라면, $\frac{b}{a}$ 을 올림한 정수가 단위 분수의 분모가 될 수 있다.

분모가 커지면 커질 수록 분수의 값은 작아지기 때문에, $\frac{b}{a}$ 보다 같거나 큰 정수 중 가장 작은 값이 가장 큰 단위분수의 분모이다.

그렇기에 나눗셈을 통해 가장 큰 단위분수를 손쉽게 알 수 있다.
하지만 이 문제의 제약으로 분모는 1,000,000보다 작아야 한다는 것이 있기 때문에, 가장 큰 단위 분수를 구한 후, 이 단위분수를 빼고 난 다음의 분모를 확인해보고, 그것이 제약에 걸리는 답이었다면 두 번째, 세 번째, ... n 번째로 큰 단위분수를 구해 확인해보는 절차를 거쳐 제약에 걸리지 않는 단위분수를 구해야 한다.

주의해야 할 점으로는 기약분수(분모, 분자의 공약수가 1)인 상태에서 문제를 풀어야 확실한 값이 나오기 때문에, 분수를 구한 뒤에는 gcd()함수로 최대공약수를 구해 약분을 진행해야 한다.

---

답안 코드 링크 (Github)

Github Solution Link

정답 코드 (C++)

#include <iostream>
#include <numeric>

using namespace std;

int main(void)
{
	long long	n, m, n_tmp, m_tmp, big, tmp_gcd;
	
	while (1)
	{
		cin >> n >> m;
		if (n == 0 && m == 0)
			break;
		while (n != 0)
		{
			big = m / n;
			if (m % n)
				big++;
			n_tmp = big * n - m;
			m_tmp = big * m;
			tmp_gcd = gcd(n_tmp, m_tmp);
			n_tmp /= tmp_gcd;
			m_tmp /= tmp_gcd;
			while (m_tmp >= 1000000)
			{
			    big++;
			    n_tmp = big * n - m;
		    	m_tmp = big * m;
			    tmp_gcd = gcd(n_tmp, m_tmp);
			    n_tmp /= tmp_gcd;
			    m_tmp /= tmp_gcd;
			}
			n = n_tmp;
			m = m_tmp;
			cout << big;
			if (n != 0)
				cout << " ";
		}
		cout << "\n";
	}
	return (0);
}