[C++ 백준 풀이][Gold I] 1016번 : 제곱 ㄴㄴ 수 (에라토스테네스의 체)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 난이도 Gold I에 해당하는 문제인 1016번 : 제곱 ㄴㄴ 수에 대한 풀이 코드와 해설을 다루고 있습니다.

 

이전에 Diamond 티어 난이도 문제인 1557번 : 제곱 ㄴㄴ 문제를 풀이한 적이 있는데, Gold 티어에도 비슷한 문제가 있어서 한 번 가지고 왔습니다.

 

[C언어 백준 풀이][Diamond V] 1557번 : 제곱 ㄴㄴ (포함과 배제의 원리 + 이진 탐색)

↑ Diamond V 난이도의 문제 풀이는 위의 링크에 정리되어 있으니 보실 분들은 참고하시면 좋을 것 같습니다.

 

그러면 이제 "1016번 : 제곱 ㄴㄴ 수"를 풀이해보도록 하겠습니다.

 

 

1016번 : 제곱 ㄴㄴ 수

 

어떤 정수가 제곱수로 나뉘지 않으면 제곱 ㄴㄴ수라고 정의한다고 가정할 때, 최솟값과 최댓값 범위 사이에서 제곱 ㄴㄴ 수가 몇 개 존재하는지를 구하는 문제입니다.

처음에는 당연히 Diamond 티어 문제 풀이 코드를 조금만 수정하면 풀릴 것이라고 생각했는데, Diamond 난이도 문제 풀이는 이 문제를 풀이하기에 너무 비효율적으로 작성되어 있었습니다. (오로지 시간 초과를 피하기 위해 일종의 노가다성 풀이로 풀었기 때문)

따라서 이 문제에서는 에라토스테네스의 체와, 범위 설정을 효과적으로 하여 문제를 풀이해보겠습니다.

 

 

↓ 위의 이미지와 동일하며, 복사하여 사용 가능한 풀이 코드는 아래 접은 글에 정리되어 있습니다.

#include <iostream>
using namespace std;

bool check[1000005] = {0, };

int main()
{
    long long Min, Max, temp, cnt = 0;
    cin >> Min >> Max;
    for(long long i=2; i*i<=Max; i++) {
        temp = Min/(i*i);
        if(Min%(i*i)) temp++;
        while(temp*i*i <= Max) {
            check[temp*i*i-Min] = 1;
            temp++;
        }
    }
    for(int i=0; i<=Max-Min; i++) if(!check[i]) cnt++;
    cout << cnt;
}

 

우선 제곱 ㄴㄴ 수 문제를 풀이해본 적이 있다면 알겠지만, 소수가 아닌 합성수의 제곱수는 이미 더 작은 소수들의 제곱수로 나뉘기 때문에 다룰 필요가 없습니다.

그렇다면 소수의 제곱수만 따지면 되는데, 문제에서 min의 범위는 최대 10^12까지 주었기 때문에 이를 나눌 수 있는 수는 10^6과 비슷하거나 그보다 작은 소수의 제곱들입니다.

10^6보다 작은 소수를 구하는 과정은 시간이 오래걸리지 않으므로, 이 소수들 모두에 대해 조사를 해도, 시간 초과에 걸리지 않습니다.

 

일단 이렇게 범위를 생각했으면 이제 어떻게 효율적으로 코드를 작성할 수 있을지 고민해보면 되는데, 문제에서 min과 max 사이의 범위가 최대 100만을 넘지 않는다고 한 것을 발견할 수 있습니다.

그러면 범위를 Min ~ Max로 잡고 계산하면 100만 개의 수만을 조사하면 되기 때문에 메모리 초과와 시간 제한에 걸리지 않습니다.

(check이라는 배열의 i번째 칸은 Min+i라는 수가 제곱 ㄴㄴ 수인지를 저장하는 배열로 사용하면 됩니다.)

 

먼저 위의 for문에서, temp*i*i는 Min과 같거나 바로 위의 제곱 ㄴㄴ 수가 아닌 수입니다.

에라토스테네스의 체를 이용하여 그보다 큰 제곱 ㄴㄴ 수가 아닌 수들을 모두 지워나가줍니다.

이 때 메모리 초과없이 배열에 접근하기 위해서 위에서 언급했던대로 "배열의 i번째 칸 = Min+i라는 수의 정보를 저장"하는 용도로 사용합니다.

 

모두 지운 후에는 제곱 ㄴㄴ 수가 아닌 수들을 1로 check 배열에 저장했으므로, check가 0인 값들만 골라서 출력해주면 이들은 모두 제곱 ㄴㄴ 수에 해당합니다.

 

 

채점을 해보면 위와 같이 약 16ms라는 길지 않은 시간에 채점이 완료된 것을 확인할 수 있습니다.

문제에서 Min과 Max 사이의 범위를 작게 준 점을 이용해서, 배열을 선언하고 또 이 배열에 접근하는 방식을 적절히 조작해서 활용하는 아이디어가 인상깊었던 문제였습니다.