[BOJ 백준 1300번 - K번째 수] 해설

 

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

1300번: K번째 수

백준 1300번 - K번째 수

문제 설명

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.
배열 A와 B의 인덱스는 1부터 시작한다.

접근법

이 문제는 브루트 포스로 접근하면 O(n^2)으로 시간초과가 일어난다. 그래서 다른 방법이 필요하다. 
먼저 n이 4일 때를 고려해보자. 

\	1	2	3	4
1	1	2	3	4
2	2	4	6	8
3	3	6	9	12
4	4	8	12	16

여기서 k가 8이라 하자. 그렇다면 우리는 크기 16인 B배열에서 8번째 원소를 찾아야 한다. 
여기서 살짝 관점을 달리해서 생각해보면, 우리가 구하는 것은 8번째로 작은 원소이지만, 그것은 '구하는 원소보다 작거나 같은 숫자는 7개만 있어야 한다'로 볼 수 있다. 

그렇다면 우리는 어떤 수 m보다 작거나 같은 수가 k-1개만 존재하는 수 m을 구하면 되는 것이다. 
m은 어떻게 구할 수 있을까?

다시 본론으로 돌아가자. k는 8이다. 이제 자신보다 작거나 같은 수가 7개 있는 어떤 수를 찾으면 된다. 
m을 2라 가정해보자. 그렇다면 2보다 작거나 같은 수는 다음의 푸른 글씨와 같다.

\	1	2	3	4	2보다 작거나 같은 수의 개수
1	1	2	3	4	2
2	2	4	6	8	1
3	3	6	9	12	0
4	4	8	12	16	0

총 3개로, 7개보다 적다. 그 뜻은 구하고자 하는 숫자, 즉 m이 원하는 것보다 작다는 뜻이다. 이제 조금 키워서 m에 6을 넣어보자. 

\	1	2	3	4	6보다 작거나 같은 수의 개수
1	1	2	3	4	4
2	2	4	6	8	3
3	3	6	9	12	2
4	4	8	12	16	1

총 12개로 7개보다 많다. 그 뜻은 구하고자 하는 숫자, 즉 m이 원하는 것보다 작다는 뜻이다. 이제 8번째 원소는 2와 6사이에 있음을 알 수 있다. 이런 방식, 즉 이분탐색으로 범위를 줄여가며 찾으면 찾는 과정은 O(logn)이 된다. 

그렇다면 이분탐색 과정에서 각 행에서 m보다 작은 수의 갯수는 어떻게 구할 수 있을까?
잘 생각해보면 각 행들은 i * 1, i * 2, i * 3, ... i * j이다. 이것을 역으로 생각해보면 m을 i로 나눈 몫이 그 행에서 m 이하의 수의 갯수이다. 하지만 이 개수는 N을 넘을 수 없기 때문에 정리하면 min(m/i, N)이 된다. 그리고 합을 구하면서 비교하는 과정을 합하면 총 시간복잡도는 O(nlogn)이 된다. 

 

정답 코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, k;
    cin >> n >> k;
    int s=1, e=k, m, sum, p=0;
    while(s<=e){
        m=(s+e)/2;
        sum = 0;
        for(int i=1;i<=n;i++)
        	sum += min(m/i, n);
        if(sum<k)
            s = m+1;
        else{
            p=m;
            e=m-1;
        }
    }
    cout << p;
}