백준 Swift [1934] 최소공배수

난이도

브론즈 I

 

문제

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

1934번: 최소공배수

 

내 답안

for _ in 1...Int(readLine()!)! {
    let input = readLine()!.split(separator: " ").map { Int($0)! }

    let a = input.min()!
    let b = input.max()!

    // 최소공배수 = 두 자연수의 곱 / 최대공약수
    var commonFactor = [Int]()

    for i in 1...a {
        if a % i == 0 && b % i == 0 {
            commonFactor.append(i)
        }
    }

    print(a * b / commonFactor.max()!)
}

• 문제 설명에 최대공약수만 구해도 최소공배수를 바로 알 수 있다는 말이 있었다.
  https://math100.tistory.com/141 글을 참고로, 두 자연수의 곱 = 최대공약수 * 최소공배수 관계를 알 수 있었고
  여기서 최소공배수를 구한다는 것은 두 자연수의 곱 / 최대공약수이기 때문에 최대공약수를 구하는 방향으로 가게 되었다.
• 최대공약수는 두 수 중 작은 수보다 크면 안되기 때문에 비교를 쉽게 하기 위해 sort 대신 a는 input의 min(), b는 input의 max()를 넣었고, for문을 사용하여 1부터 a까지의 수 중 두 수를 나눴을 때 나머지가 0인 수를 commonFactor 배열에 추가하도록 하였다.
• 이 작업이 끝나면 위에서 언급한 두 자연수의 곱(a * b) / 최대공약수(commonFactor.max())를 출력하며 마무리하였다.