[백준 / BOJ] 1300번 : K번째 수 - JAVA

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

1300번: K번째 수

매개변수 탐색

알고리즘 분류에 보면 "이분 탐색"과 "매개변수 탐색"이라고 적혀있는 것을 볼 수 있다. 이 문제는 아이디어가 도저히 떠오르지 않아 분류를 참고했는데, 매개변수 탐색이 큰 힌트가 됐다.

 

보통 이분 탐색을 통해 도출한 값 자체를 조건으로 해서 start값과 end값을 조절한다. 하지만 매개변수 탐색에서는 이분 탐색으로 도출한 값을 다시 함수에 매개변수로 넣고, 해당 함수 결과 값으로 start값과 end값을 조절하게 된다. 비슷한 문제로는 공유기 설치가 있다.

 

우선 start = 1, end = N * N으로 값을 두고 매번 갱신하도록 한다. 갱신 조건은 (start + end) / 2로 나온 값 mid보다 작은 원소 개수이다.

long cnt = 0;
for (int i = 1; i <= N; i++) {
    cnt += Math.min(mid / i, N);
}

mid / i 는 j 값을 나타낸다. 예를 들어 mid가 5이고, i가 2라면 5 / 2 = 2 열까지가 mid보다 작다는 뜻이다. 단, N이 mid보다 작을 수도 있기 때문에 Math.min(mid / i, N)으로 두었다.

 

if(cnt >= K) {
    end = mid - 1;
} else {
    start = mid + 1;
}

위에서 탐색한 값 cnt를 통해 start와 end를 조절해준다. 만일 cnt가 K보다 작다면, mid 값이 더 커져야 mid와 같거나 작은 값이 더 많아질 것이다. 따라서 start = mid + 1를 해준다.

 

반대로, cnt가 K보다 크거나 같다면 mid를 줄인다. 해당 조건을 만족하는 가장 작은 값을 구해야 하기 때문에 break을 하지 않고 계속 진행하게 된다. (가장 작은 값을 구하는 이유는 배열에 속한 값을 구해야 하기 때문이다.)

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 시간 : 124ms
// 메모리 : 11560KB
public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		long N = Long.parseLong(br.readLine());
		long K = Long.parseLong(br.readLine());
		
		long start = 1;
		long end = N * N;
		
		while(start <= end) {
			long mid = (start + end) / 2;
			
			long cnt = 0;
			boolean flag = false;
			for (int i = 1; i <= N; i++) {
				cnt += Math.min(mid / i, N);
			}
			
			if(cnt >= K) {
				end = mid - 1;
			} else {
				start = mid + 1;
			}
		}
		
		System.out.println(start);
	}

}