[프로그래머스/c++] 분수의 덧셈

<문제>

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

 

<유형>

정수론

 

<풀이>

기약 분수를 덧셈하는 방식은, 분모를 최소공배수로 맞춘 다음 분자를 더한다. 

#include <string>
#include <vector>

using namespace std;

int gcd(int a, int b){
	int n;

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

int lcm(int a, int b){
    return a * b / gcd(a, b);
}

vector<int> solution(int denum1, int num1, int denum2, int num2) {
    vector<int> answer;
    answer.assign(2, 0);
    
    answer[1] = lcm(num1, num2);
    if(answer[1] / num1 != 0) {
        denum1 *= (answer[1] / num1);
    }
    if(answer[1] / num2 != 0) {
        denum2 *= (answer[1] / num2);
    }
    
    answer[0] = denum1 + denum2;
    
    return answer;
}

하지만 이 방식으로는 1/3의 정답만 얻을 수 있었다. 뭐가 문제일까?

정답은 마지막 answer의 값이 약분이 되었을 경우를 고려하지 않았기 때문이다.

 

답이 (9,15)라면 (3, 5)로 변환해야한다는 것.

 

그럼, 코드 하단에 약분하는 코드를 추가하면 된다.

 

#include <string>
#include <vector>

using namespace std;

int gcd(int a, int b){
	int n;

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

int lcm(int a, int b){
    return a * b / gcd(a, b);
}

vector<int> solution(int denum1, int num1, int denum2, int num2) {
    vector<int> answer;
    answer.assign(2, 0);
    
    answer[1] = lcm(num1, num2);
    if(answer[1] / num1 != 0) {
        denum1 *= (answer[1] / num1);
    }
    if(answer[1] / num2 != 0) {
        denum2 *= (answer[1] / num2);
    }
    
    answer[0] = denum1 + denum2;
    
    int temp = gcd(answer[1], answer[0]);
    
    if (temp != 1) {
        //약분이 되는 경우
        answer[0] /= temp;
        answer[1] /= temp;
    }
    
    return answer;
}

썩 괜찮은 코드는 아니지만, 정답을 맞췄다.