0-1. 분수의 덧셈

 

 

1. 문제

첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

 

2. 코드

 

#include <string>
#include <vector>

using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

vector<int> solution(int numer1, int denom1, int numer2, int denom2) {
    vector<int> answer;
    
    int denom = (denom1 * denom2);
    int numer = (numer1 * denom2) + (numer2 * denom1);
    int common = gcd(numer, denom);
    
    denom /= common;
    numer /= common;

    answer.push_back(numer);
    answer.push_back(denom);
    return answer;
}

 

3. 분석

기약분수는 더 이상 통분되지 않는 분수를 뜻한다.

즉 분자와 분모가 공약수를 가지지 않게 되면 (최대 공약수로 분자와 분모를 나누어) 기약분수가 된다.

따라서 최대 공약수를 구하는 gcd 함수를 정의한다.

gcd는 분모를 분자로 계속 나누어 나머지가 0일 때 까지 반복한다.

 

이후에 denom에는 두 분수를 통분한 분모의 값, numer에는 통분한 분자의 값을 대입하고, 최대 공약수로 나누어주면 된다.