[백준] 1735번 : 분수 합 (C언어 / C99)

문제

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

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

 

 

입력

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

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

- 시간 제한: 2초 이내 / 메모리 제한: 128MB 이내

 

코드 (C99)

#include <stdio.h>

//프로토타입 선언부
long long gcd(long long a, long long b);

main()
{
	long long first_denominator, first_child;
	long long second_denominator, second_child;

	scanf("%lld %lld", &first_child, &first_denominator);
	scanf("%lld %lld", &second_child, &second_denominator);

	long long result_child, result_denominator;
	
	result_denominator = first_denominator * second_denominator;
	result_child = first_child * second_denominator + second_child * first_denominator;

	long long mod = gcd(result_child, result_denominator);

	printf("%lld %lld", result_child / mod, result_denominator / mod);

	return 0;
}

long long gcd(long long a, long long b)
{
	if (b == 0)
		return a;
	else
		return gcd(b, a % b);
}

 

---

여담

 

처음에는 아래와 같이 풀었다.

물론 정답이긴 하다. 위 코드와 다른점은 gcd를 따로 함수로 구현하느냐 그렇지 않느냐의 차이이다.

 

아래의 코드를 제출하려던 찰나에 gcd를 찾는 함수를 구현하면 코드가 좀더 깔끔해지겠다는 생각이 들었다.

그래서 좀더 깔끔하게 하기 위해 함수를 만들고 코드 일부분을 수정하였다.

 

다만, 아래의 코드는 gcd 를 찾는 함수에 비해 조금 느리다.

#include <stdio.h>
#include <math.h>

main()
{
	long long first_denominator, first_child;
	long long second_denominator, second_child;

	scanf("%lld %lld", &first_child, &first_denominator);
	scanf("%lld %lld", &second_child, &second_denominator);

	long long result_child, result_denominator;

	result_denominator = first_denominator * second_denominator;
	result_child = first_child * second_denominator + second_child * first_denominator;

	long long mod = (result_child < result_denominator) ? result_denominator : result_child;

	for (long long i = 1; i <= (long long)sqrt(mod) + 1; i++) //gcd 찾기
	{
		if (result_child % i == 0 && result_denominator % i == 0)
		{
			result_child /= i;
			result_denominator /= i;
			i = 1;
		}
	}
	printf("%lld %lld", result_child, result_denominator);

	return 0;
}

 

 

코드가 이상하거나 이해되지 않는 부분이 있다면 댓글 남겨주세요! + 더 좋은 풀이 방법이 있다면 알려주세요 :)