백준 1016번(G1) - 제곱ㄴㄴ수 풀이 정리 (Incomplete)

Programming, Baekjoon

백준 1016번 오답노트 Incomplete

Posted Dec 26, 2021

백준 1016 : 제곱ㄴㄴ수

어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다.

min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

제한

1 ≤ min ≤ 1,000,000,000,000 -> 10^12
min ≤ max ≤ min + 1,000,000

풀이과정

처음 접근한 방법은 소수를 구하고 그 소수의 제곱수를 구한 뒤 제곱수의 배수들(제곱ㅇㅇ수)을 구하여 전체 개수 (max-min+1) 에서 제곱ㅇㅇ수들을 뺄 생각이었음.

제곱수란 n²를 n의 제곱수라고 함.

하지만 역시나 bad_alloc 문제가 발생하였고, 이 때는 정리를 하지 못해서 또 다시 같은 실수를 반복하였음.

메모리 할당 문제나 자료형 오버플로우 문제를 다시 겪었음.

우선 메모리 할당 문제부터 해결한 방식은 1456번 거의 소수문제와 동일하게 내가 구해야 하는 소수의 범위만큼만 할당해주면 되는 것임.

따라서 최대값이 10¹²+10⁶ 정도이므로 10⁶이나 10⁷ 정도로 size를 b값에 따라 정하였음. (최대 할당 크기는 10^8까지 가능함.)

  
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef unsigned long long int uli;

int main() 
{
    ios::sync_with_stdio(false); 
    cin.tie(NULL);
	
    uli s,b;
    cin >> s >> b;
	
    uli size = (b <= 1000000) ? b+1 : 1000001; /* 메모리 할당 문제 해결 */
    vector<bool> check(size, true);
    uli cnt= (s == 1) ? b : b-1;
    for(uli i=2; i<size; i++) 
    {
        for(uli j=i*2; j < size; j+=i) 
        {
            check[j]=false;
        }
         uli k=i*i;
         while(k<=b)
         {
            if(k>=a) {cnt++;}
            k+=i*i;                           /* 중복문제 발생 */
         }
    }
    cout << cnt << '\n';
    return 0;
}

위 코드의 문제점은 제곱수들의 배수에는 중복되는 값이 있다는 것임. 예를 들면, 200은 4의 배수이자 25의 배수임.

따라서 중복되는 값을 배열의 인덱스로 구분하고자 하더라도 최대 할당 가능한 크기는 10^8이므로 배열의 인덱스 값으로 해당 값이 제곱ㅇㅇ수인지 비교하는 방법은 할 수 없음.

젤 큰 문제점은 중복을 어떻게 구분하는지가 문제였음.

이 문제를 어떻게 해결해야 하는지 고민해봤지만, 배열의 인덱스 값을 이용해서 하는 방법 외에 생각나는 방법이 없었음..

질문 게시판 중에 cpp코드가 있었는데 그 코드를 보고 알게 되었음.

깨달은 사실은 꼭 배열의 인덱스 값 i가 숫자 i를 뜻해야 하는가 ? 이다.

min 값이 만약 1이 아니라 10^5등 큰 값이 들어온다면, 기존의 방식으로는 할당은 가능할지라도 메모리 낭비가 너무 크게 되며, 10^9가 min이라면 할당도 못하게 됨.: 즉, arr[1]이 숫자 1을 뜻하는 것이 아니라 arr[0]이 min값에 해당하면 된다는 것, min이 10^9라면 arr[0]이 10^9를 뜻하면 된다는 것임.

제곱ㄴㄴ수를 0으로, 제곱ㅇㅇ수를 1로 구분한다고 하면 10^9가 만약 제곱ㅇㅇ수라면 arr[0]=1로 나타내면 된다는 것임.

또한 min이 10^9라고 할 때, 4부터 시작해서 10^9 이상의 제곱ㅇㅇ 수를 찾으려고 하면 너무나 오래 걸리게 됨.

따라서 min을 제곱수로 나누어서 만약 나머지가 0이라면, 그 값부터 시작해서 카운트를 하고 0이 아니라면 그 다음 값인 min/(i*i)+1부터 시작해서 카운트를 해서 시간을 단축할 수 있음.

  
uli ans[1000001]={};

/* main */
uli k=s/(i*i);              /* min/(i*i) */
if(s%(i*i) != 0) { k++;}    /* min%(i*i) 검사 */
while(i*i*k <= b) 
{
    ans[(i*i*k)-s]=1;       /* 제곱ㅇㅇ 수이면 arr[제곱수의 배수-min]=1 */
    k++;
}

ans 배열의 크기는 10^6 이상의 값들은 제곱하면 10^12에 근접하거나 넘어가게 되므로 10^6까지만 설정하여 구하면 됨. (추측이며 맞지 않을 가능성이 높음)

ans[s-s] = ans[0]으로 생각하면 됨.

최종 결론

굳이 소수를 구하여 풀 필요는 없어서 날렸음.

이 문제를 풀면서 겪은 문제는 중복되는 값에 대해서 어떻게 구분을 할 수 있는지, 배열의 크기를 얼마나 설정해야 하는지, 배열의 인덱스로 제곱ㅇㅇ수를 중복을 피하면서 어떻게 카운트 하는지 였음.

깨달은 점은 배열의 인덱스 값이 그 숫자만 뜻하는 것만은 아니라는 점..

  
#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long int uli;

uli ans[1000001]={};

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL);
	
    uli s,b, cnt=0;
    cin >> s >> b;
    uli size = (b < 1000000) ? b+1 : 1000001; 
    for(uli i=2; i<size; i++) 
    {
        uli k=s/(i*i);
        if(s%(i*i) != 0) { k++;} 
        while(i*i*k <= b) 
        {
            ans[(i*i*k)-s]=1;
            k++;
        }
    }
    for(uli i=0; i<= b-s; i++) 
    {
        if(ans[i] != 1) { cnt++; }
    }
    cout << cnt << '\n';
    return 0;
}

위 코드의 문제점이 있는데 min=1, max=1,000,001,000,000 일 때, 배열의 없는 인덱스에 접근하게 되므로 에러 발생하게 되는데 배열의 크기를 최대한 늘려도 안 될 것임.

따라서 질문을 하였고 그 답변으로 O(sqrt(N))의 시간으로 가능하다는 답변과 링크를 하나 받았음.

링크로 들어가보면 N번째 Square-Free Number를 구하는 방법에 대해서 질문한 글이 나오는데 답변으로 N까지의 Square-Free Numbers를 찾는 방법에 대해 설명하고 있음.

방법을 정리하면 다음과 같음.

Square-Free Numbers

Link: 제곱_인수가_없는_정수

Square-Free Number란 소인수분해를 했을 때, 제곱인수가 없는 숫자를 뜻한다.

즉, 1이 아닌 제곱수를 인수로 갖지 않는 양의 정수.

소인수분해를 하면 소수의 곱으로 이루어져 있는데 이때 같은 소수가 여러 개가 아니고 각각 다른 소수의 곱으로 이루어져 있다는 뜻이다.

예를 들면 15 = 3x5 이므로 Square-Free Number이다.

소수는 Square-Free인가? 소수는 Square-Free Numbers이다.

Inclusion-Exclusion Principle

Link: 포함배제의_원리

포함-배제의 원리란 유한 집합 내에서 합집합의 원소의 개수를 세는 기법이라고 하며, 조합론에서 널리 쓰이는 근본적인 기법이다.

정의를 살펴보면 뫼비우스 함수가 사용되었다.

풀이 정리

Link: ohgym.tistory.com/19; blog.naver.com/programmer18/220415532678

사실 제곱ㄴㄴ수 문제는 Square-Free Number라는 꽤 유명한 문제라고 한다.

이 문제를 풀기 위해선 포함-배제의 원리를 이용해서 해결해야 한다.

위의 링크에 있는 내용을 정리하면 다음과 같음.

이 문제는 일정 구간 내에 있는 Square-Free Numbers의 개수를 구하는 문제로 F(n) = N까지의 Square-Free Numbers의 개수라고 하면 일정 구간 내의 Square-Free Numbers의 개수는 F(MAX) - F(MIN-1)이다.

따라서 N보다 작은 소수들의 제곱수들로 나누면 4의 배수의 개수, 9의 배수의 개수 등등을 바로 구할 수 있다.

나도 이 방법을 생각했었지만, 중복되는 값을 어떻게 구분해야 하는가에 대한 문제에 막혀 못 풀었었다..