백준 1735번: 분수 합 #C

문제

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

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

입력

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

 

출력

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

 

 

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

 

 

문제만 보면 가볍게 최대공약수를 구한 후 기약분수로 나타내어서 출력하면 되는 문제처럼 보였다.

 

하지만 네 자연수의 최댓값은 30,000이며 이 문제의 시간 제한은 2초이다.

 

 

#include <stdio.h>

int minm(int a, int b)
{
    return a > b ? b : a;
}

int main()
{
    int a,b;
    int A,B;
    scanf("%d %d %d %d",&a,&b,&A,&B);

    int tp,bt;
    tp = a*B + A*b;
    bt = b * B;
    int m = minm(tp,bt);
    for(int i =2; i<m; i++)
        {
           if(tp%i==0 && bt%i==0)
           {
               tp/=i;
               bt/=i;
               i-=1;
           }
        }
    printf("%d %d", tp, bt);
    return 0;
    
}

 

이 코드가 필자가 처음에 작성해본 코드이다, 매우 간단한 코드인데, 처음에 주어진 분수 a/b 와 A/B를 통분한다.

--> 이 코드의 경우 두 분수의 최소공배수를 구하지 않고 분모를 단순히 b*B만을 구했다, 이부분에서 시간 제한 요소에 걸린 것으로 추정된다.

 

이후 코드를 보면 minm이라는 함수를 통해서 tp,bt의 최솟값을 구하는데, 이 과정은 두 수의 최대공약수를 구하기 위해서 어느 수가 더 크고 작은지를 알아야 했기 때문이다.

 

두 수중 더 작은 값을 구한후 for구문을 사용해서 최대공약수를 구해 tp,bt을 구해 출력했지만 백준에서는 시간 초과가 나왔다.

 

 

아무래도 통부하는 과정에서 최소공배수를 구해야만 풀 수 있는 문제인 것 같아서 더 조사해보니 ,

gcd 라는 유클리제 호제법

이 나왔다. 유클리제 호제법은 최대공약수. 최대공배수를 수학적인 알고리즘 방법을 통해 쉽게 구할수 있는 알고리즘이다.

 

다음시간에는 유클리제 호제법을 배워보고 직접 코드를 짜봐서 이번시간에 못 풀었던 1735번 문제를 풀어보도록 하겠다.

 

유클리제 호제법을 사용한 풀이법

 

 

#include <stdio.h>
int Euclid(int a,int b)
{
    int x = (a>b)? a : b;
    int y = (a>b)? b : a;

    if(y==0)
    {
        return x;
    }
    else{
        return(Euclid(y,x%y));
    }
}


int main()
{
    int a,b;
    int A,B;
    scanf("%d %d %d %d",&a,&b,&A,&B);
    int tp=a*B+A*b;
    int bt=b*B;
    int num = Euclid(tp,bt);
    printf("%d %d",tp/num , bt/num);
    return 0;
    

    
}

 

이 코드를 통해 문제를 풀이할 수 있었다,

 

기존 main()부분의 코드는 이전에 시간초과가 되었던 코드와 거의 동일하지만 Encllid라는 함수가 새로 추가되었다.

 

이 함수가 바로 유클리드 호제법을 사용한 코드이다.

 

 

int Euclid(int a,int b)
{
    int x = (a>b)? a : b;
    int y = (a>b)? b : a;
    
// 큰 수를 X에 두고 작은 수를 Y에 두어야만 오류가 나지 않는다.

    if(y==0)
    {
        return x;
    }
    else{
        return(Euclid(y,x%y));
    }
}

 

 

실질적인 구현 코드는 if, else구문이 전부이다, 그 이전 코드의 경우 유클리드 호제법에서 큰수와 작은 수를 구분하는 코드이다.

 

if(y==0)
    {
        return x;
    }
else{
        return(Euclid(y,x%y));
    }

 

코드를 살펴보면 두 수 x,y가 같은 수가 될때까지 계속해서 큰수를 작은 수로 나눈 나머지를 반환한다.

 

숫자로 예를 들어보자면

 

✅ 순서 정리

함수의 최대공약수 검색 단계

 

1	Euclid(48, 18)	48 % 18 = 12	Euclid(18, 12)
2	Euclid(18, 12)	18 % 12 = 6	Euclid(12, 6)
3	Euclid(12, 6)	12 % 6 = 0	Euclid(6, 0)
4	Euclid(6, 0)	y == 0 → return 6	✅ 최대공약수 찾음

 

 

주어진 숫자가 48,18인 경우에는 이러한 과정을 거쳐서 6이라는 최대 공약수를 찾게 된다.

 

 

 

추가적으로 위키백과에 있는 유클리드 호제법 C언어 코드를 첨부해보겠다.

 

int gcd(int a, int b)
{
    int c;
	while(b)
	{
		c = a % b;
		a = b;
		b = c;
	}
    return a;
}