본문 바로가기

BOJ/C++

[BOJ] 분수의 합

[문제]

https://www.acmicpc.net/problem/1735

 

1735번: 분수 합

첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다.

www.acmicpc.net

[풀이]

1735 맞았습니다!! 1988 0 C++14 / 수정 1100 35초 전

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
 
using namespace std;
 
//분수 합
//최대공약수, 최소공배수 계산 필요 
 
int findGCD(int a, int b) {
    int c;
 
    while(b!=0) {
        c = a%b;
        a = b;
        b = c;
    }
    return a;
}
 
int findLCM(int a, int b) {
    return a*/ findGCD(a, b);
}
 
int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int a, b, c, d;
 
    cin >>>> b>>c>>d;
    // a/b
    // c/d
 
    /*
        기약분수 = 분자 분모의 최대 공약수가 1인 분수 
        두 분수를 더하는 법 -> 분모의 최대 공배수를 구하고 분자에 곱해준다. 
    */
 
    int gcd = findGCD(a, b);
    if (gcd != 1) {
        //최대공약수 존재 
        a /= gcd;
        b /= gcd;
    }
 
    gcd = findGCD(c,d);
    if (gcd != 1) {
        //최대공약수 존재 
        c /= gcd;
        d /= gcd;
    }
 
    int lcm = findLCM(b, d);
    //분모끼리의 최대공배수 구함 
    
    a *= lcm / b;
    c *= lcm / d;
 
    gcd = findGCD((a+c), lcm);
    //합쳐진 분자 분모끼리의 최대 공약수를 구함 
 
    if (gcd != 1) {
        int tmp = (a+c)/gcd;
        lcm /= gcd;
        cout << tmp << " "<< lcm << '\n';
    }
    else {
        cout << (a+c) << " "<< lcm << '\n';
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

'BOJ > C++' 카테고리의 다른 글

[BOJ] 배열 돌리기4  (0) 2019.08.16
[BOJ] 안전영역  (0) 2019.08.16
[BOJ] 플로이드  (0) 2019.08.09
[BOJ] 타임머신  (0) 2019.08.09
[BOJ] 최단 경로  (0) 2019.08.09