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

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 난이도 Diamond V에 해당하는 문제인 1557번 : 제곱 ㄴㄴ 문제에 대한 풀이 코드와 해설을 다룹니다.

 

Solved.ac에서 어려운 문제들은 어떤 수준일지 궁금해서 Diamond 티어 문제들을 살펴보다가 그나마 해결 수가 가장 많은 문제를 한 번 시도해보기로 했습니다.

 

Diamond 티어 문제까지는 사실 필수적인 알고리즘 공부에는 적절하지 않은 난이도로 알고 있어서 새로운 알고리즘을 사용하는 문제라면 안 풀었겠지만, 1557번 제곱 ㄴㄴ 문제의 경우에는 알고리즘 분류가 정수론, 이진 탐색, 포함과 배제의 원리로 되어있어서 시도해볼만 하다고 생각되어서 풀었습니다.

 

 

1557번 : 제곱 ㄴㄴ

 

제곱수를 약수로 가지지 않는 수를 제곱 ㄴㄴ수라고 정의할 때, K번째 제곱 ㄴㄴ수를 출력하는 문제입니다.

시간 제한이 2초이고 K의 입력 범위가 10억 이하이기 때문에 시간을 단축시킬 수 있는 코드를 고안해야 합니다.

 

 

#include<stdio.h>
#define INT_MAX 2147483647
#define SQRT_INT_MAX 46340

long long int sieve[50000] = {0, }, sq[50000];
long long int K, order, check, count = 0, low, mid, high, key;

int order_of_K(int K) {
    order = K;
    for(int i=0; i<count; i++) {
        order -= K/sq[i];
        for(int j=i+1; j<count && sq[i]*sq[j]<=INT_MAX; j++) {
            order += K/(sq[i]*sq[j]);
            for(int k=j+1; k<count && sq[i]*sq[j]*sq[k]<=INT_MAX; k++) {
                order -= K/(sq[i]*sq[j]*sq[k]);
                for(int l=k+1; l<count && sq[i]*sq[j]*sq[k]*sq[l]<=INT_MAX; l++) {
                    order += K/(sq[i]*sq[j]*sq[k]*sq[l]);
                    for(int m=l+1; m<count && sq[i]*sq[j]*sq[k]*sq[l]*sq[m]<=INT_MAX; m++) {
                        order -= K/(sq[i]*sq[j]*sq[k]*sq[l]*sq[m]);
                        for(int n=m+1; n<count && sq[i]*sq[j]*sq[k]*sq[l]*sq[m]*sq[n]<=INT_MAX; n++) {
                            order += K/(sq[i]*sq[j]*sq[k]*sq[l]*sq[m]*sq[n]);
                        }
                    }
                }
            }
        }
    }
    return order;
}

int main() {
    scanf("%d", &K);
    for(int i=2; i*i<=SQRT_INT_MAX; i++)
        for(int j=2; i*j<=SQRT_INT_MAX; j++) sieve[i*j] = 1;
    for(int i=2; i<=SQRT_INT_MAX; i++) if(!sieve[i]) sq[count++] = i*i;
    low = K, high = 2*K;
    while(low <= high) {
        mid = (low + high)/2;
        key = order_of_K(mid);
        if(key == K) {
            while(order_of_K(--mid) == K) ;
            printf("%d", ++mid);
            return 0;
        }
        else if(key < K) low = mid + 1;
        else if(key > K) high = mid - 1;
    }
}

 

이 문제를 해결하는 데에는 여러 가지 핵심 포인트들을 인지해야하기 때문에 중요 개념별로 나눠서 정리했습니다.

 

1. 수의 범위

K가 클수록 당연히 연산 시간도 길어지므로, K의 최댓값인 10억을 기준으로 생각해보면 됩니다.

K가 10억 이하이고 4의 배수와 9의 배수 등 소수 제곱의 배수들이 모두 지워지면 많아도 10억번째 제곱 ㄴㄴ수는 INT_MAX 이하라고 추론하였습니다. (여기서 논리가 명확하지 않아서 아쉽긴 합니다.)

그러면 나누는 제곱 ㄴㄴ수는 아무리 커도 INT_MAX에 제곱근을 씌운 약 46340 이하입니다.

이를 SQRT_INT_MAX라고 두고 이보다 작은 소수들을 먼저 구했습니다. (5만 이하의 소수들을 구하는 데에는 시간이 거의 걸리지 않지만 배운 것을 써볼 겸 에라토스테네스의 체를 사용했습니다.)

 

2. 모든 제곱수를 저장하지 말고 소수 제곱수만 저장하기

예를 들어 2^2=4의 배수들을 지워나갔으면 4^4=16의 배수나 6^6=36의 배수들은 알아서 지워지기 때문에 고려할 필요가 없습니다.

소수 제곱수끼리는 서로소이기 때문에 서로를 곱해서 나오는 최소공배수만 고려해주면 됩니다.

 

3. K번째 제곱 ㄴㄴ수를 구하지 말고 K가 몇 번째 제곱 ㄴㄴ수인지 구하기

K번째 제곱 ㄴㄴ수를 바로 구하는 것은 불가능하지만 K가 몇 번째 제곱 ㄴㄴ수인지는 구할 수 있습니다.

K보다 작은 제곱수의 배수들이 N개라고 하면 K는 (K-N)번째 제곱 ㄴㄴ수가 되기 때문입니다.

따라서 여러 개의 정수에 대해 몇 번째 제곱 ㄴㄴ수인지를 구해가면서 범위를 좁혀 K번째가 되는 어떤 수를 찾으면 됩니다.

 

4. 이진 탐색 활용

수의 증감과 몇 번째 제곱 ㄴㄴ수인지 그 order의 증감은 같기 때문에 순서대로 확인할 수도 있지만 시간의 단축을 위해 이진 탐색을 활용해야 합니다.

저는 K와 2K를 양 경계로 잡고 이진 탐색을 수행하였습니다.

 

5. 포함과 배제의 원리

포함과 배제의 원리는 고등학교 수학을 이수했으면 알고 있겠지만 간략히 서술하겠습니다.

4의 배수, 9의 배수, 25의 배수들을 지우면 36(=4*9)의 배수, 100(=4*25)의 배수, 225(=9*25)의 배수들은 두 번씩 지워지기 때문에 이들을 다시 더해줘야 합니다.

36의 배수, 100의 배수, 25의 배수들을 다시 더하면 900(=4*9*25)의 배수들이 결과적으로 한 번 더 더해지기 때문에 마지막에 한 번 빼줘야 합니다.

이런 식으로 조합으로 나오는 배수들을 더하고 빼서 개수를 맞추는 과정에 포함과 배제의 원리가 필요합니다.

 

6. 연산을 최소화하는 반복문 조건 설정

위 코드의 order_of_K 함수에 구현된 6중 for문의 조건문을 참고하시면 됩니다.

변수는 바깥 루프 변수+1에서 시작하며, 소수 제곱수들을 곱한 값이 20억을 넘으면 즉시 반복문을 종료하도록 합니다.

예를 들어 1, 2, 6번째 수를 곱해서 범위를 넘었으면 1, 2, 7번째 곱부터는 무조건 범위를 넘어가게 되고, 그 다음 루프에서 1, 3, 4번째 수부터 곱하므로 모든 경우의 수가 빠짐없이 고려됨을 알 수 있습니다.

7번째 루프부터 필요없는 이유는 가장 작은 7개의 소수 제곱수를 곱해봐도 (4*9*25*49*121*169*289) 20억을 훨씬 넘습니다.

 

7. 예외

저도 처음에 6번까지만 고려하고 제출했다가 틀려서 당황했는데, 확인하면서 1부터 대입해보다가 3을 대입하니 4가 나옴을 알게 되었습니다. (원래 3번째 제곱 ㄴㄴ수는 3임)

이것은 왜 그러냐면, K가 N개의 소수제곱수 약수를 가지고, K+1가 N+1개의 소수제곱수 약수를 가진 상황에서, 이진 탐색을 하다가 K+1을 먼저 찾을 경우 이러한 오류가 나타납니다. (K+1이 아니라 K를 출력해야 함)

(이진 탐색이 앞에서부터 검사하는 것이 아닌 중간마다 뛰어서 검사하기 때문에 발생하는 예외)

따라서 key를 발견해도 그 앞의 수가 역시 K에 해당하지는 않는지 확인해야 합니다.

이에 대한 검사 과정은 위의 코드에서 while(order_of_K(--mid) == K) ; 부분에 해당합니다.

 

 

 

위의 코드를 제출하면 약 12ms 정도의 양호한 작동 시간이 나옵니다.

 

+ 다른 분들은 어떻게 풀었나 대충 봤는데 저와 비슷한 수준으로 푸신 분들이 대부분이었습니다.

심지어는 변수명도 비슷하던데 6중으로 반복문 쓰다가 코드가 너무 길어져서 다들 저랑 똑같은 생각을 하신듯 싶습니다.