[Programmers] 120808번 분수의 덧셈

문제설명

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

제한사항

0 <numer1, denom1, numer2, denom2 < 1,000

문제풀이

유클리드 호제법

두 양의 정수 a,b (a>b)a,b (a>b)에 대하여 a=bq+r (0≤r<b)a=bq+r(0≤r<b)이라 하면, a,ba,b의 최대공약수는 b,rb,r의 최대공약수와 같다. 즉, gcd⁡(a, b)=gcd⁡(b, r)
gcd(a, b)=gcd(b, r)에서 r=0이라면, a,b의 최대공약수는 b가 된다.

풀이 과정

1. 분모와 분모를 곱한다.
2. 분자에 다른 분수의 분모를 곱한다.
3. 곱한 두 분수를 더한다.
4. 유클리드 호제법을 이용하여 분자와 분모의 최대공약수를 구한다.
5. 최대공약수로 분자와 분모를 나누어 answer 벡터에 넣고 반환한다.

소스코드

#include <string>
#include <vector>

using namespace std;

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

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

    int gcd = GCD(numer, denom);
    answer.push_back(numer/gcd);
    answer.push_back(denom/gcd);
    return answer;
}