최대공약수와 최소공배수Permalink

문제 링크Permalink

최대공약수와 최소공배수

분석Permalink

문제 그대로 최대공약수와 최소공배수를 구하고 반환하는 문제입니다.

해당 문제에서는 브루트포스로 풀이하지 않겠습니다.

최대공약수는 유클리드 호제법을 사용해 구할 수 있습니다. 저는 유클리드 호제법을 사용해서 풀이해봤습니다.

최소공배수는 최대공약수를 사용해야하며, 공식은 아래와 같습니다.

$LCM(a, b) = \frac{|a \cdot b|}{GCD(a, b)}$

어느정도 오버플로우를 방지할 수 있는 코드로 작성하면 다음과 같습니다.

(a / std::gcd(a, b)) * b

C++17버전 이상에서는 std::gcd함수로 최대공약수를 std::lcm함수로 최소공배수를 구할 수 있지만 직접 구현해서 풀어보겠습니다.

풀이Permalink

#include <vector>

std::vector<int> solution(int n, int m) {
    std::vector<int> answer;
    
    int a = (n > m) ? n : m;
    int b = (n > m) ? m : n;
    
    while(b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    
    int gcd = a;
    
    answer.push_back(gcd);
    answer.push_back((n / gcd) * m);
    
    return answer;
}

반복문에서는 유클리드 호제법을 사용해 최대공약수를 구합니다.

answer.push_back((n / gcd) * m)에서 최소공배수를 구하고 값을 대입합니다.

성능 요약Permalink

테스트 1 〉 통과 (0.01ms, 4.14MB)
테스트 2 〉 통과 (0.01ms, 3.67MB)
테스트 3 〉 통과 (0.01ms, 4.07MB)
테스트 4 〉 통과 (0.01ms, 4.21MB)
테스트 5 〉 통과 (0.01ms, 4.28MB)
테스트 6 〉 통과 (0.01ms, 3.67MB)
테스트 7 〉 통과 (0.01ms, 4.21MB)
테스트 8 〉 통과 (0.01ms, 4.15MB)
테스트 9 〉 통과 (0.01ms, 4.2MB)
테스트 10 〉 통과 (0.01ms, 4.16MB)
테스트 11 〉 통과 (0.01ms, 4.2MB)
테스트 12 〉 통과 (0.01ms, 4.21MB)
테스트 13 〉 통과 (0.01ms, 4.44MB)
테스트 14 〉 통과 (0.01ms, 4.16MB)
테스트 15 〉 통과 (0.01ms, 4.14MB)
테스트 16 〉 통과 (0.01ms, 4.21MB)