K번째 수( BOJ 1300 )

문제 : https://www.acmicpc.net/problem/1300

1300번: K번째 수

 

문제 파악하기

2차원 배열 A[i][j]의 값을 정렬하여 1차원 배열 B[i]로 변환한 다음, K번째 숫자를 출력하는 문제입니다. 가장 쉬운 방법이라면 1차원 배열 B를 만든 다음, 2차원 배열 A에 있는 모든 값을 저장한 후 정렬하여 B[K]를 출력하면 됩니다. 하지만 이 문제는 배열의 크기가 최대 100,000*100,000 = 10,000,000,000(100억)까지 커질 수 있습니다. 이런 경우에는 배열을 직접 만들어서 풀 수는 없습니다. 이 경우, 어떤 방법이 있을까요?

 

문제 해결하기

이 문제에서 우리가 중점적으로 봐야할 내용은 바로 배열 B가 정렬된 상태라는 점입니다. 정렬이 된 배열이라면 우리는 1가지 알고리즘을 떠올릴 수 있습니다. 바로 이분 탐색입니다. 그럼 이 문제를 이분 탐색으로 풀 수 있을지 확인해봅시다. 우선 문제를 표면적으로 본다면 이분 탐색으로 풀 수 없습니다.

 

그렇다면 이 문제를 결정 문제로 바꿔봅시다. 결정 문제란 결괏값이 0 또는 1로 나오는 것을 의미하며, 문제를 결정문제로 바꾸는 것은 마치 스무고개처럼 여러 번의 질문을 통해 문제의 정답을 찾는 과정을 의미합니다. 이 문제를 결정문제로 바꿀 수 있을까요? 정답은 Yes 입니다. 우리는 K번째 숫자를 찾고 싶습니다. 그렇다면 우리는 어떤 숫자 T 앞에 (K-1)개의 숫자가 있는가? 라는 문제로 바꿀 수 있습니다. 이렇게 문제를 바꾸면 우리가 할 일은 단 한 가지 입니다. 숫자 T를 적절하게 선택하여 앞에 있는 숫자의 개수를 세면 됩니다. 그리고 이 때, 사용하는 알고리즘이 바로 이분 탐색입니다. T는 1부터 N*N(혹은 10억) 사이의 숫자이기 때문에 절반씩 줄여가면 logN번만에 우리가 원하는 숫자를 찾을 수 있습니다.

 

그럼 우리가 선택한 T 앞에 몇 개의 숫자가 있는지는 어떻게 알 수 있을까요? 이건 사실 한번씩 확인해보는 방법밖에 없습니다. 다만, 우리는 항상 N보다 작거나 같은 숫자들의 배수만이 배열 B에 저장될 수 있다는 걸 알고 있습니다. 그렇기에 숫자 T에 대해 1부터 N까지 한번씩 확인해보면서 T보다 작은 배수를 총 몇 개 만들 수 있는지 확인하면 됩니다. 예를 들어 N=5인 경우, 배열 B에는 다음과 같이 숫자들이 저장됩니다.

 

N=5) 1 2 2 3 3 4 4 4 5 5 6 6 8 8 9 10 10 12 12 15 15 16 20 20 25

 

N이 5일 때, 정답이 될 수 있는 숫자는 1 ~ 25(5²) 사이의 숫자입니다. 이 경우, 처음에는 가운데 숫자인 13을 선택하여 앞에 총 몇 개의 숫자가 있는지 확인해봅니다. 13보다 작은 숫자는 총 몇 가지일까요?

 

5의 배수 : 5*1, 1*5, 5*2, 2*5 (총 4개)

4의 배수 : 4*1, 1*4, 4*2, 2*4, 4*3, 3*4 (총 6개)

3의 배수 : 3*1, 1*3, 3*2, 2*3, 3*3 (총 5개)

2의 배수 : 2*1, 1*2, 2*2 (총 3개)

1의 배수 : 1*1 (총 1개)

 

N이 5이기 때문에 5의 배수부터 세보면 총 19개의 숫자가 있다는 걸 알 수 있습니다. 이를 다음과 같이 수식으로 바꿀 수도 있습니다.

 

5의 배수 : 13/5 >> 1, 2 / 2*2 = 4개

4의 배수 : 13/4 >> 1, 2, 3 / 3*2 = 6개

3의 배수 : 13/3 >> 1, 2, 3 / 2*2 + 1 = 5개

2의 배수 : 13/2 >> 1, 2 / 1*2 + 1 = 3개

1의 배수 : 13/1 >> 1 / 1*1 = 1개

 

수식으로 바꾸면서 눈여겨 볼 점은 항상 자기 자신을 곱한 값보다 작은 배수만을 세어주어야 한다는 점입니다. 예를 들어 13보다 작은 3의 배수는 3, 6, 9, 12로 총 4개 있습니다. 여기서 12이라는 숫자는 3*4로 만들 수 있으며, 4라는 숫자는 3보다 큰 숫자이기 때문에 제외시켜 주어야 합니다. 제외시키지 않는다면 중복으로 값을 세어 정확한 개수를 구할 수 없습니다.

 

이렇게 우리가 선택한 숫자 T 앞에 몇 개의 숫자가 있는지는 1부터 N까지의 배수 중 T보다 작은 배수의 개수를 세어주면 됩니다. 그리고 나온 개수를 바탕으로 K보다 작은지 큰지에 따라 탐색의 범위를 좁혀주면 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <algorithm>
#define NMAX 100010
#define INF 1000000000
using namespace std;
 
int N, K;
 
long long int l, r, mid;
long long int tmp, t;
 
bool isPossible(int num) {
    for(int i=1;i*i<=num;i++) {
        if(num%i) continue;
 
        if(i<=N and num/i<=N) return 1;
    }
 
    return 0;
}
 
int main() {
    scanf("%d", &N);
    scanf("%d", &K);
 
    l = 1;
    if(1LL*N*N > INF) r = INF;
    else r = N*N;
 
    while(l<=r) {
        mid = (l+r)/2;
 
        tmp = 0;
                for(int i=N;i>=1;i--) {
                    t = mid/i;
                    
                    if(t < i) tmp += t*2;
                    else tmp += i*2-1;
                }
 
        if(tmp < K) l = mid+1; 
        else r = mid-1;
        
    }
 
    while(!isPossible(l)) l++;
 
    printf("%lld", l);
 
}

후기

이분 탐색을 연습하는데 이만큼 좋은 문제는 없다고 생각합니다. 결정 문제로 바꾸는 과정도 쉽사리 떠오르지 않으며, 바꾼 후에도 앞에 있는 숫자의 개수를 세는 알고리즘을 만드는 것도 쉽지 않은 문제라 이분 탐색 심화 문제로 추천하고 싶습니다.