[백준 BOJ] 1016. 제곱 ㄴㄴ 수

난이도

Gold I

문제 풀이

제곱 ㄴㄴ수를 찾는게 쉬울까 아니면 제곱수로 나누어지는 수들을 찾는게 쉬울까? 전자는 그 수보다 작은 제곱수들로 모두 나누어봐야 알 수 있겠지만, 후자는 제곱수의 배수들만 찾아주면 된다. 따라서 후자가 더 쉽다는 판단하에 문제를 풀었다. 이 문제를 풀기 위해 제곱수들로 나누어지는 수들을 모두 찾아내면 되는데, 이 과정이 소수들을 찾을 때 에라토스테네스의 체(Eratosthenes’s Sieve)를 사용하는것과 유사하다. 즉, 나는 에라토스테네스의 체를 살짝 변형해 제곱수의 배수들을 지워나가는 식으로 체를 만들면 된다고 생각했다.

이 문제 잘 보면, max값이 \(\small 10^{12} + 10^{6}\)까지 주어질 수 있다. 그렇기에, 소수들을 찾을때처럼 bool 배열을 \(\small 10^{12} + 10^{6}\) 만큼의 크기로 만들게 된다면, 당연히 메모리 초과가 일어난다. 우리가 필요한건 min과 max사이에 몇개의 제곱 ㄴㄴ수가 있는지 궁금하니 \(\small max - min + 1\)개 만큼만 정보가 필요하다는 것을 알 수 있다. 그래서 최대 \(\small 10^{6} + 1\) 크기의 배열로 문제를 해결할 수 있도록 하면 된다. 단순히, min부터 인덱스를 0으로 생각하고 풀면 된다는 소리이다. 구현을 한다면 아래의 코드처럼 할 수 있다.

void solve(ll m, ll M) { //m == min, M == max
    vector<bool> isJegopNoNo(M - m + 1, true);

    for(ll i = 2; i <= sqrt(M); ++i) {
        ll k = ceil(double(m) / double(i * i));
        
        for(ll j = (i * i) * k; j <= M; j += (i * i)) {
            isJegopNoNo[j - m] = false;
        }
    }

    int ret = 0;
    for(int i = 0; i < isJegopNoNo.size(); ++i) {
        if(isJegopNoNo[i]) ret++;
    }

    cout << ret;
}

이때, ll은 long long이다 (int형 범위를 넘어가기 때문에 int보다 큰 자료형으로 해주어야 overflow가 일어나지 않는다.).

바깥쪽 루프를 보면 \(\small \sqrt{M}\)까지만 돌게 되는데, \(\small \sqrt{M}\)보다 큰 수를 제곱하면 M보다 커지기 때문에 검사해줄 필요가 없기 때문이다. 어떤 제곱수 \(\small i^{2}\)의 배수가 min값 보다 클 때, 숫자들을 지워야 하는데, 이를 위해서 간단한 부등식을 생각해보자. \(\small i^{2} \cdot k \geq min\) 인데, 이를 만족하는 k의 최소값이 \(\left \lceil \frac {m}{i^{2}} \right \rceil\) 이다. 따라서 저 값부터 시작해 \(\small i^{2}\)을 더해주며 배수를 지우면 된다.

모든 제곱수의 배수를 지우고 나서 남은 수들이 제곱 ㄴㄴ수임이 자명하므로, 그 수들의 개수를 세어 출력해주면 끝이다.

나는 처음에 예상치 못한 에러로 디버깅을 조금 했는데, 그 이유는 바깥쪽 루프에 초기값을 long long이 아닌 int로 해놨었기 때문에 오버플로우가 났었다. \(\small \sqrt{M}\)값이 int범위라는것만 생각하고 있었기에 제곱에 대해서 전혀 고려를 안했는데, 이를 깨닫고 long long로 고치니 해결됐다… 이런 어처구니 없는 실수를 조심하도록 하자..

코드 전문

1016 // 제곱 ㄴㄴ 수