[1735] 분수 합(C#)

알고리즘 : 유클리드 호제법
난이도 : Silver Ⅲ

유클리드 호제법을 활용하여 푸는 문제.

유클리드 호제법(Division algorithm) 이란?
주로 큰 두 수의 최대공약수를 파악하기 힘든 경우에
먼저 '큰 수'를 '작은 수'로 나눈 나머지를 구한 뒤
'나눴던 수'를 그 '나머지'로 나누는 과정을 되풀이하여
최종적으로 나머지가 0이 될 때 마지막 계산에서 나누는 수로서 최대공약수를 얻을 수 있다.

예를 들면 아래와 같다.

string[] strFirstFraction = Console.ReadLine().Split(' ');
string[] srtSecondFraction = Console.ReadLine().Split(' ');

int[] firstFraction = Array.ConvertAll(strFirstFraction, int.Parse);
int[] secondFraction = Array.ConvertAll(srtSecondFraction, int.Parse);

int commonDenom = 0;

if (firstFraction[1] != secondFraction[1])
    commonDenom = firstFraction[1] * secondFraction[1];
else
    commonDenom = secondFraction[1];

int[] resultFraction = new int[2];

if (commonDenom == secondFraction[1])
{
    resultFraction[0] = firstFraction[0] + secondFraction[0];
    resultFraction[1] = commonDenom;
}
else { 
    resultFraction[0] = firstFraction[0]*secondFraction[1] + secondFraction[0]*firstFraction[1];
    resultFraction[1] = commonDenom;
}

int gdc = resultFraction[0];
int remainder = Math.DivRem(resultFraction[1], resultFraction[0]).Remainder;
while (remainder != 0)
{
    int thisremainder = Math.DivRem(gdc, remainder).Remainder;
    gdc = remainder;
    remainder = thisremainder;
}

Console.WriteLine(resultFraction[0]/gdc + " " + resultFraction[1]/gdc);