[Swift 알고리즘] 백준 1735 분수 합

×

수학, 정수론, 유클리드 호제법 Silver 3

백준 1735 분수 합

Euclidean algorithm 유클리드 호제법

: 두 양의 정수의 최대공약수를 구하는 방법

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

 

이걸 이제야 알다니.. 반성합시다

// 유클리드 호제법 69104KB 8ms
let first = readLine()!.split(separator: " ").compactMap { Int($0) }
let second = readLine()!.split(separator: " ").compactMap { Int($0) }

var denominator = first[1] * second[1]
var numerator = first[0] * second[1] + first[1] * second[0]

let divider = gcd(numerator, denominator)
print(numerator / divider, denominator / divider)

func gcd(_ a: Int, _ b: Int) -> Int {
    print(a, b)
    if b == 0 {
        return a
    } else {
        return gcd(b, a % b)
    }
}

 

 

이거 안쓰고 푸니까 당연히(?) 시간 초과 뜸

30000 이하 자연수니까 3만 * 3만 = 9억 -> 최악의 경우 4.5억번 반복문 돌아야,,,

// 시간초과
let first = readLine()!.split(separator: " ").compactMap { Int($0) }
let second = readLine()!.split(separator: " ").compactMap { Int($0) }

var denominator = first[1] * second[1]
var numerator = first[0] * second[1] + first[1] * second[0]

// 약수 찾기
let range = min(denominator, numerator) / 2
for i in (2..<range).reversed() {
    if denominator % i == 0, numerator % i == 0 {
        denominator /= i
        numerator /= i
    }
}

print("\(numerator) \(denominator)")