[C++] 소수 최소 공배수 (백준 21919번)

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

 

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<int> a = vector<int>(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int cnt = 0;
    long long ans = 1;

    for (int x: a) { //!
        bool isPrime = true;
        double tmp = sqrt(x);
        if (tmp * tmp == x) {
            isPrime = false;
        }
        else {
            for (int i = 2; i <= tmp; i++) {
                if (x % i == 0) {
                    isPrime = false;
                    break;
                }
            }
        }

        if (isPrime) {
            ans *= x;
        }
    }

    if (ans == 1) {
        ans = -1;
    }

    cout << ans << '\n';
}

첫번째 풀이이다. 문제에서 시키는 대로, 수열 a에서 소수만 골라 그들의 최소 공배수를 구하려고 했다. 근데 생각해보니 소수들끼리는 공약수가 존재하지 않기 때문에 소수들의 '최소 공배수 == 소수들을 전부 곱한 값'이다. 그래서 소수만 잘 구하면 되겠다고 생각했다.

그런데 처음에 생각이 든 대로, 수열 a의 각 수마다 2부터 하나씩 나눠가며 소수를 확인하도록 코드를 짜서 제출하니 시간 초과가 떴다. 진짜 어떻게 해도 시간 초과가 나왔다. (오답)

 

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    vector<bool> isPrime = vector<bool>(1000001, true);
    isPrime[1] = false;
    for (int i = 2; i < 1001; i++) {
        int tmp = 2 * i;
        while (tmp < 1000001) {
            isPrime[tmp] = false;
            tmp += i;
        }
    }

    int n;
    cin >> n;

    vector<int> a = vector<int>(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    set<int> pn;
    for (int x: a) { //!
        if (isPrime[x]) {
            pn.insert(x);
        }
    }

    long long ans = 1;
    for (int x: pn) {
        ans *= x;
    }

    if (ans == 1) {
        ans = -1;
    }

    cout << ans << '\n';
}

두번째 풀이이다. 계속 시간 초과가 나던 중, 에라토스테네스의 체가 생각났다. 일단 가능한 모든 수에 대해서 소수를 모두 구해 놓은 상태로 푸는 방법이다. 크기가 1000001인 벡터 isPrime을 만들고, 전체에서 2의 배수 지우고, 3의 배수 지우고, ... 이런식으로 소수가 아닌 것들을 전부 걸러내 소수만 남긴다. 그러면 수열 a의 각 원소별로 isPrime이 true인지 false인지만으로 소수를 판정할 수 있는 것이다. 이렇게 하면 시간 안에 문제를 해결할 수 있다. 

추가로 주의할 점은 같은 수가 여러번 들어올 수 있다는 것이다. 수열 a의 각 원소들을 하나씩 살펴볼 때, 소수이면 바로 ans에 곱하는 것이 아니라, 일단 집합 pn에 넣어두고 마지막에 pn의 원소들을 곱해야 중복되는 수 없이 올바른 값을 구할 수 있다. (정답)

 

---

 

실버5~실버1 랜디 문제였다. 실랜디도 나에겐 어렵다.. 흑흑 푸는데 한 시간 걸림. 암튼 실력을 키워가면서 범위도 높여가야 할 것 같다. 

 

[참고] 백준 랜덤 디펜스 하는법

solved.ac 검색 창에 다음과 같은 형식으로 입력하기!

ex) *s5..s1 s#100.. -@$me : 실버5~실버1 문제 중 100명 이상이 해결하였으며 내가 풀지 않은 문제