Silver_III 난이도의 C++ 문제를 풀이한 내용입니다. 두 분수를 입력받아 더한 후, 기약분수 형태로 출력하는 문제입니다.

백준 1735: 분수 합

Silver_III 난이도의 C++ 문제를 풀이한 내용입니다. 두 분수를 입력받아 더한 후, 기약분수 형태로 출력하는 문제입니다.

문제 소개

문제 번호: 1735
문제명: 분수 합
난이도: Silver_III
사용 언어: C++
실행 시간: 0 ms
메모리: 2020 KB
문제 요약: 두 개의 분수 $a / b$ 와 $c / d$ 가 주어졌을 때, 이 두 분수를 더한 결과를 기약분수 형태로 출력하는 문제입니다.

접근 방법

이 문제는 기본적인 분수 덧셈과 기약분수로 만드는 과정을 이해하면 쉽게 해결할 수 있습니다.

분수 덧셈: 두 분수 $a / b$ 와 $c / d$ 를 더하는 공식은 다음과 같습니다.
$\frac{a}{b} + \frac{c}{d} = \frac{a \times d + b \times c}{b \times d}$
따라서, 새로운 분수의 분자는 $a \times d + b \times c$ 가 되고, 분모는 $b \times d$ 가 됩니다.
기약분수 만들기: 분수 덧셈 결과로 나온 분수를 기약분수 형태로 만들기 위해서는 분자와 분모를 최대공약수(GCD, Greatest Common Divisor)로 나누어야 합니다. 최대공약수를 구하기 위해 유클리드 호제법을 사용합니다.

선택한 알고리즘/자료구조

유클리드 호제법 (Euclidean Algorithm): 두 정수의 최대공약수를 효율적으로 계산하기 위해 사용했습니다.
기본적인 정수 연산: 분자, 분모 계산 및 나눗셈 연산을 사용합니다.

방법 선택 이유

분수 덧셈의 기본적인 수학적 공식을 직접 적용하는 것이 가장 직관적이고 효율적인 방법입니다. 또한, 결과를 기약분수로 만들어야 하므로 최대공약수를 구하는 유클리드 호제법이 필수적으로 사용됩니다.

풀이 과정

입력 받기: 두 분수의 분자와 분모, 총 네 개의 정수 $a, b, c, d$ 를 입력받습니다.
분수 덧셈 수행: 입력받은 값들을 사용하여 분수 덧셈 공식을 적용합니다.
- 새로운 분자의 값: numerator = a * d + b * c
- 새로운 분모의 값: denominator = b * d
최대공약수(GCD) 계산: 위에서 계산된 numerator와 denominator의 최대공약수를 gcd 함수를 이용하여 구합니다.
기약분수 변환: 계산된 최대공약수 g로 numerator와 denominator를 각각 나누어 기약분수를 만듭니다.
- numerator /= g
- denominator /= g
결과 출력: 변환된 numerator와 denominator를 공백으로 구분하여 출력합니다.

핵심 아이디어

분수의 덧셈 공식을 그대로 적용하고, 최대공약수로 나누어 기약분수를 만드는 것입니다.

주의할 점

분자, 분모 계산 시 오버플로우가 발생하지 않도록 자료형을 적절히 선택해야 합니다. (본 문제에서는 int로 충분합니다.)
유클리드 호제법 구현 시 0으로 나누는 경우를 고려해야 하지만, 분모는 항상 양수이므로 문제 되지 않습니다. (GCD 함수의 y != 0 조건이 이를 처리합니다.)

코드 설명

#include <iostream>
using namespace std;

// 최대공약수(GCD) 함수: 유클리드 호제법
int gcd(int x, int y) {
    while (y != 0) {
        int tmp = y;
        y = x % y;
        x = tmp;
    }
    return x;
}

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d; // 두 분수 a/b, c/d 입력

    // 분수 합 공식: a/b + c/d = (a*d + b*c) / (b*d)
    int numerator = a * d + b * c; // 분자 계산
    int denominator = b * d;       // 분모 계산

    // 분자와 분모의 최대공약수 계산
    int g = gcd(numerator, denominator);

    // 분자와 분모를 최대공약수로 나눠 기약분수로 만들기
    numerator /= g;
    denominator /= g;

    // 결과 출력 (기약분수 형태)
    cout << numerator << " " << denominator << "\n";

    return 0;
}

주요 부분 설명

gcd(int x, int y) 함수: 유클리드 호제법을 사용하여 두 정수 x와 y의 최대공약수를 반환합니다. y가 0이 될 때까지 x를 y로 나눈 나머지를 새로운 y로, 이전 y를 새로운 x로 갱신하며 반복합니다.
main 함수:
- cin >> a >> b >> c >> d;: 네 개의 정수를 입력받아 첫 번째 분수는 $a / b$ , 두 번째 분수는 $c / d$ 로 저장합니다.
- int numerator = a * d + b * c;: 분수 덧셈 공식에 따라 새로운 분자의 값을 계산합니다.
- int denominator = b * d;: 분수 덧셈 공식에 따라 새로운 분모의 값을 계산합니다.
- int g = gcd(numerator, denominator);: 계산된 분자와 분모의 최대공약수를 gcd 함수로 구합니다.
- numerator /= g; denominator /= g;: 최대공약수로 분자와 분모를 각각 나누어 기약분수로 만듭니다.
- cout << numerator << " " << denominator << "\n";: 최종적으로 얻은 기약분수의 분자와 분모를 출력합니다.

복잡도 분석

시간 복잡도:
- 분자, 분모 계산: $O (1)$
- GCD 계산 (유클리드 호제법): 두 수 $N, M$ 에 대해 $O (lo g (min (N, M)))$ 입니다. 이 문제에서는 분자의 최대값은 대략 $1 0^{9} \times 1 0^{9} = 1 0^{18}$ (만약 입력값이 매우 크다면, long long을 써야 하지만, 일반적인 int 범위에서는 $1 0^{9}$ 정도입니다. 여기서는 int로 충분하다고 가정합니다.) 분모는 $1 0^{9} \times 1 0^{9} = 1 0^{18}$ 정도가 될 수 있으므로, GCD 계산은 매우 빠르게 수행됩니다.
- 전체 시간 복잡도는 GCD 계산 시간에 의해 지배되며, $O (lo g (분자 \times 분모))$ 입니다.
공간 복잡도:
- 변수 저장을 위한 공간만 사용하므로 $O (1)$ 입니다.

배운 점

분수 덧셈의 기본적인 수학적 원리를 코드로 구현하는 방법을 배웠습니다.
기약분수로 만들기 위해 최대공약수(GCD)의 중요성을 다시 한번 확인했습니다.
유클리드 호제법을 C++로 구현하는 방법을 익혔습니다.
정수형 오버플로우에 대한 가능성을 염두에 두고, 문제의 입력 범위에 따라 적절한 자료형(int, long long 등)을 선택하는 것이 중요함을 알게 되었습니다. (이 문제에서는 int로 충분했습니다.)

이 문제는 기본적인 알고리즘과 수학적 지식을 결합하여 해결하는 좋은 예시입니다. 다른 분수 관련 문제나 수론 문제를 접할 때 유용하게 활용될 수 있습니다.