[BOJ] 1300번 - K번째 수

1300번 - K번째 수

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	10661	3750	2774	38.336%

문제

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

배열 A와 B의 인덱스는 1부터 시작한다.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 ${10}^5$보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다.

k는 min(${10}^9$, ${N}^2$)보다 작거나 같은 자연수이다.

출력

B[k]를 출력한다.

제한

예제 입력 1

3
7

예제 출력 1

6

 

 

출처

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

 

알고리즘 분류

• 이분 탐색

접근 방법

이 문제는 $O(N^2)$의 시뮬레이션 방식으로는 풀 수 없는 시간복잡도를 가지고 있다. 즉 $O(NlogN)$이하의 알고리즘으로 풀어야함을 알 수 있다.

 

어떻게 접근해야 할까?

먼저 결정문제로 바꿀 수 있는 문제인지 확인해보니, [ ß(x) = N*N 배열에서 x 이하의 수가 k개 이상 있니? ] 라고 함수를 잡았을 때 배열 B는 오름차순 정렬되어있다는 조건이 있으므로, ß(x)는 특정 값을 기준으로 참/거짓으로 이분화 된다는 것을 알 수 있다.

이 사실을 통해서 ${ß(x) = true}$ 를 만족하는 x중 최소 값을 찾으면 이것이 x라는 수가 나오는 첫번째 인덱스라는 사실을 알 수 있다.

 

Parametric Search 를 이용해보자

일단 우리는 value 의 후보가 1~${N^2}$ 까지임을 알고 있다.

ƒ(x)를 x라는 수가 처음으로 나타나는 인덱스 라고 가정하자.( 배열 B가 정렬되어 있으므로, ƒ(x)는 ƒ(x) <= ƒ(x+1) 관계를 가지는 단조함수라고 볼 수 있다. ==> parametric search 사용가능! )

그러면, ƒ(x) 가 K보다 크다면, x라는 수는 B라는 배열을 정렬했을 때 K번째 수보다 크다는 사실을 알 수 있다. 그리고 ƒ(x)가 K보다 작다면, x라는 수는 B라는 배열을 정렬했을 때 K번째 수 보다 작다는 사실을 알 수 있다. 이를 통해서 Parametric Search를 수행하면 x는 최적해에 근사해지는 것을 알 수 있다. < 이산적 변량이므로, 근삿값이 최적해라고 볼 수 있다 > 

 

그렇다면 ƒ(x)를 $O(N^2)$미만으로 어떻게 구현해야하는가?

먼저 알아둬야할 점은 i*j의 쌍으로 이루어진 값은 1~i*j에 존재하는 모든 자연수를 포함하지 않는다.

우리는 이 값들을 구하는것이 목적이 아니라 특정 값(value) 미만의 i*j 쌍의 값의 개수를 구하고자 한다.

아래 표를 통해서 이해해보자.

 

ex) N = 5, K = 16

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

i*j < 16 을 만족하는 pair는 i의 값을 1부터 N까지 순회하면서 구할 수 있다.

i = 1일때, j = 16 미만의 수 : 16개 ==> 하지만 최대 개수는 (N=5)개를 넘을 수 없다.

i = 2일때, j = 8 미만의 수  : 8 개 ---> 하지만 최대 개수는 (N=5)개를 넘을 수 없다.

i = 3일때, j = 5.xx 미만의 수 : 5개 

i = 4일때, j = 4 미만의 수: 3개

i = 5일때, j = 3.xx 미만의 수 : 3개

 

이를 일반화 하면 i가 1~N까지 루프를 돌 때마다  min(N, K/i) 을 더해주는 방식으로 구현하면 ƒ(x)의 시간복잡도를 $O(N)$으로 줄일 수 있다.

 

Parametric Search를 하는 데에 ${O(logN)}$의 시간과 해의 참/거짓 여부를 확인하기 위한 findIdx 함수의 시간 복잡도는 ${O(N)}$이므로, 총 시간 복잡도는 ${O(N*logN)}$이 된다.

소스 코드

#include <bits/stdc++.h>
using namespace std;

long long findIdx(long long size, long long value){
    // Idx는 1부터 시작
    long long idx = 1;
    for(int i=1; i<=size; i++){
        idx += min( size, value/i );
    }
    return idx - 1; // 자기 자신 제외
}

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	long long N, K;
	cin >> N >> K;

	long long left = 1, right = N*N;

	long long ans = 1e9;
	// f(x) : x라는 수가 나오는 최초의 인덱스(최소 인덱스), 단조함수 만족
	while( left <= right ){
	    long long mid = (left+ right)/2;
	    long long firstIdx = findIdx(N, mid);

	    if( firstIdx >= K ){
	        ans = mid;
	        right = mid - 1;
	    }
        else
            left = mid + 1;
	}
    cout << ans;
    return 0;
}