프로그래머스 입문 120808 분수의 덧셈

문제

출처

두 분수의 분자와 분모가 길이 4의 배열에 순서대로 담겨 있다.
두 분수를 더한 결과를 기약분수로 나타냈을 때의 분자와 분모를 배열로 반환하라.

풀이

#include <stdlib.h>

int compute_gcd(int a, int b)
{
    int remainder;

    while (b != 0)
    {
        remainder = a % b;
        a = b;
        b = remainder;
    }

    return a;
}

int* solution(int numer1, int denom1, int numer2, int denom2)
{
    int numerator = numer1 * denom2 + numer2 * denom1;
    int denominator = denom1 * denom2;
    int greatest_common_divisor = compute_gcd(numerator, denominator);

    int* result = (int*)malloc(sizeof(int) * 2);

    result[0] = numerator / greatest_common_divisor;
    result[1] = denominator / greatest_common_divisor;

    return result;
}

분수의 덧셈을 하려면 먼저 분모를 같게 만들어야 한다.
사람은 두 분수를 보면 다음처럼 필요한 만큼만 통분해서 계산한다.

$$\frac{1}{2} + \frac{3}{4} = \frac{2}{4} + \frac{3}{4} = \frac{5}{4}$$

하지만 코드에서는 두 분모의 관계를 매번 따져서 최소한으로 통분하려고 하면 구현이 복잡해진다.
그래서 이 풀이는 두 분모를 그대로 곱해서 공통 분모를 만든다.

$$\frac{1}{2} + \frac{3}{4} = \frac{4}{8} + \frac{6}{8} = \frac{10}{8}$$

분모가 denom1 * denom2가 되면 첫 번째 분자는 numer1 * denom2가 되고, 두 번째 분자는 numer2 * denom1이 된다.
따라서 더한 분자는 numer1 * denom2 + numer2 * denom1로 계산할 수 있다.

이렇게 구한 분수는 정답의 형태가 아닐 수 있다.
문제에서는 결과를 기약분수 형태로 요구하기 때문이다.
기약분수는 분자와 분모의 최대공약수가 1인 분수다.
즉 계산한 분자와 분모를 둘의 최대공약수로 나누면 기약분수가 된다.

최대공약수는 유클리드 호제법으로 구한다.
예를 들어 21과 56의 최대공약수는 다음처럼 구한다.

a	b	몫	나머지
21	56	0	21
56	21	2	14
21	14	1	7
14	7	2	0

먼저 a를 b로 나눈 나머지를 구한다.
다음 반복에서는 a 자리에 이전의 b가 들어가고, b 자리에 이전의 나머지가 들어간다.
이 과정을 b가 0이 될 때까지 반복하면 최대공약수 7을 구할 수 있다.