백준 21919 - 소수 최소 공배수

백준 21919 문제 바로가기

풀이

길이가 N인 수열에서 소수(prime)를 골라 최소공배수를 구하는 문제이다.

소스 코드

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

typedef long long LL;
const LL MAX = 1000000;

int N;
bool isPrime[MAX + 1];

LL gcd(LL a, LL b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

LL lcm(LL a, LL b) {
    return a * b / gcd(a, b);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    for (int i = 2; i <= MAX; ++i) {
        isPrime[i] = true;
    }
    for (LL i = 2; i * i <= MAX; ++i) {
        if (isPrime[i]) {
            for (LL j = i + i; j <= MAX; j += i) {
                isPrime[j] = false;
            }
        }
    }

    cin >> N;
    vector<int> primes;
    for (int i = 0; i < N; ++i) {
        int k;
        cin >> k;
        if (isPrime[k]) {
            primes.push_back(k);
        }
    }

    if (primes.size() < 2) {
        cout << -1;
    }
    else {
        LL ans = 1;
        for (int k : primes) {
            ans = lcm(ans, k);
        }
        cout << ans;
    }
    return 0;
}

리뷰 및 후기

틀린 부분 - 1

문제에서 수열 A의 원소의 최댓값은 $10^{6}$임에 유의한다.

소수 판별을 할 때 에라토스테네스의 체를 사용하였다.

typedef long long LL;
...
for (int i = 2; i <= MAX; ++i) {
    isPrime[i] = true;
}
for (LL i = 2; i * i <= MAX; ++i) {
    if (isPrime[i]) {
        for (LL j = i + i; j <= MAX; j += i) {
            isPrime[j] = false;
        }
    }
}

두 번째 반복문의 i * i에서 정수형 오버플로가 발생할 수 있다는 점을 생각하지 못하고 오답 판정을 받았다. long long 타입을 사용하도록 수정하였다.

틀린 부분 - 2

수열 A에 동일한 값의 소수가 존재할 수 있으며, 최소공배수를 구해야 하는 문제의 본질에 집중해야 한다.

일단 수열에서 소수의 최소공배수를 구하는 것은 수열에서 소수만 곱하는 것과 동일하다. 이러한 생각을 갖고 수열에서 소수를 모두 곱하는 형태로 구현하여 오답 판정을 받았다.

수열 A에서 소수가 중복된 값의 소수가 존재할 수 있다는 점에 유의해야 한다.

6
2 2 3 5 6 8

최소 공배수를 구하는 것이므로 입력이 위와 같을 때 30이 나와야 한다. 단순하게 수열에서 소수를 모두 곱하는 형태로 구현하면 60이 나와서 오답 판정을 받는다.

문제의 요구사항은 정확히 파악했으나 문제를 잘못 이해한 점, 그리고 구현할 때 실수할 가능성이 있는 부분에 딱 걸렸다. 반성해야겠다..