프로그래머스>코딩테스트 입문>분수의 덧셈 (C++) | 최대공약수, 최소공배수

 

나의 풀이

#include <string>
#include <vector>
#include <numeric>

using namespace std;

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

    numer = numer1 * denom2 + numer2 * denom1;
    denom = denom1 * denom2;

    gcd_num = gcd(numer, denom);
    while(gcd_num != 1) {
        numer /= gcd_num;
        denom /= gcd_num;
        gcd_num = gcd(numer, denom);
    }

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

    return answer;
}

분수의 합을 구하고 그것을 기약분수로 만들기 위해 최대공약수가 필요하다고 판단.

 

C++ STL에서 이 친구를 사용해보았다. 

- 헤더

#include <numeric>

 

- 함수

gcd() : 최대공약수 // Greatest Common Divisor

lcm() : 최소공배수 // Least Common Multiple