[cppchallenge] 3. 최소공배수 프로그램 구현하기

modern cpp challenge 책의 문제들을 푸는 과정을 작성해놓으려 한다.
 
1. 문제
2. 풀이(1)
2.1. I/O
2.2. 연산
2.3. 코드
3. 후기
 

1. 문제

최소공배수 프로그램 구현하기

양의 정수 두 개 또는 그 이상 주어졌을 때, 최소공배수를 계산하고 출력하는 프로그램을 작성하라.
 
 

2. 풀이(1)

필요한 코드 구조는 아래와 같다.
양의 정수 입력값 받는 부분 + 최소공배수 연산하는 부분 + 결과값 출력하는 부분
 
전 문제와 마찬가지로 main함수에서 I/O를 해결하고 최소공배수 연산 부분은 따로 함수로 처리하기로 했다.

 
 
2.1. I/O
최대공약수 문제와 동일하게 입력값, 출력값을 unsigned long long으로 정했다. 
 
 
2.2. 연산
최소공배수는 수에 공통으로 존재하는 배수 중 가장 작은 수를 의미한다. 그러므로 numeric 라이브러리의 gcd 함수를 사용하여 gcd를 구하고, 몫을 이루는 수들을 찾으려고 했는데 해당 방법은 gcd와 몫 사이 중복되는 수들도 있고, 배수 중 가장 작은 수를 찾는다는 목적에 적합하지 않다고 생각했다.

그래서 일단은 lcm 함수를 이용하기로 하였다. 

다시 생각해보니 lcm 함수를 이용하는 것 자체가 lcm(a, b) = (a * b) / gcd(a, b)이다. 여기서 두 수의 최소공배수는 공통 약수를 한 번씩만 포함하는데, 두 수의 곱을 최대공약수로 한 번 나누면 중복된 약수 부분이 제거되게 된다. 그러므로 내가 lcm 구하는 방법에 대해 명확하게 이해하지 못했다는 생각이 다시 한 번 들었다.
 
2.3. 코드
처음에 작성한 코드는 아래와 같다.

#include<iostream>
#include<vector>
#include<numeric>
using namespace std;

unsigned long long lcm_multiple(const vector<unsigned long long>& numbers) {
    unsigned long long result = numbers[0];
    for (size_t i = 1; i < numbers.size(); ++i) {
        result = lcm(result, numbers[i]);
    }
    return result;
}

int main() {
    int n;
    cin >> n;
    vector<unsigned long long> numbers(n);
    for (int i = 0; i < n; ++i) {
        cin >> numbers[i];
    }
    cout << lcm_multiple(numbers) << "\n";
    return 0;
}

시간복잡도는 O(nlogM)이고, 저번 문제와 다르게 cpp 표준 라이브러리 함수가 인식할 수 있도록 공식 표준 타입으로 선언했다.
 
 
 
 

3. 후기

방법만 알고 있고 해당 함수의 과정을 정확히 이해하지 못했다는 사실을 알게 되어서 해당 함수의 매커니즘을 다시 복습해보는 계기가 되었다.