[백준] 1735 분수 합 [C#]

분수 2개를 통분한 다음 더 이상 약분이 되지 않는 기약분수로 만들어서 출력해 주면 된다.

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            int[] frac1 = Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
            int[] frac2 = Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
 
            frac1[0] *= frac2[1];
            frac2[0] *= frac1[1]; // 분자 연산
 
            bool end = false;
            int num = frac1[0] + frac2[0];
            int denum = frac1[1] * frac2[1];
 
            int a = num; int b = denum; int temp = 0;
 
            while (a != 0)
            {
                temp = b % a;
                b = a;
                a = temp;
            }
            print.WriteLine($"{num / b} {denum / b}");
        }
 
    }
}

처음에는 무한루프 속에서 2부터 가장 작은 숫자까지 1씩 증가하면서 두 수의 공약수를 찾아서 두 수를 나눴다.

이 과정을 더이상 공약수가 없을 때까지 반복하는 방법을 사용했는데, 시간 초과가 나왔다.

그래서 다른 방법이 없나 찾아봤더니 유클리드 호제법이 있다고 하더라.

완전히 이해한거 같지는 않은데, 내가 이해한 바로는 B를 A로 나누어(진분수일 때만) 나머지 값을 구하고,

B를 나눈 값을(A) 나머지 값으로 나누어 다시 나머지 값을 구하는 방식으로, 나머지가 0이 나올 때까지 반복하여, 두 수의 최대공약수를 찾는 방법이라고 한다.

이 방법을 사용했더니 통과했다.