[JAVA] 백준 1300번 : K 번째 수

 

---

 

• 코드

정답 코드 : 이분 탐색을 통해 푼 코드이다. 자세한 설명은 밑에

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

public class Main {
	private static long N;
	private static long k;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Long.parseLong(br.readLine());
		k = Long.parseLong(br.readLine());
		
        long left = 1, right = k;
        long printValue = 0;
        
        // 이분 탐색 수행
        while (left <= right) {
            long mid = (left + right) / 2;
            long cnt = 0;
            
            // mid보다 작거나 같은 수는 몇 개인지 계산.
            for (int i = 1; i <= N; i++) {
                cnt += Math.min(mid/i, N);
            }
 
            if (cnt < k) {
                left = mid + 1;
            } else {
            	printValue = mid;
                right = mid - 1;
            }
        }
		
		System.out.print(printValue);
	}
}

 

• 설명

 

만약, N이 3이라 할때 A배열이다. B 배열은 (1,2,2,3,3,4,6,6,9)순서가 될 것이다.

예를들어, 4가 B배열의 몇번째 인지 찾는다고 볼때 0번째 열은 4이하가 3개, 1열은 2개, 2열은 1개이다.

총 개수는 6개이고  실제로 4는 6번째 오는 수 였습니다.

이 부분에서

count = Math.min(mid/i,N)  (i는 i번째 열을 의미)

즉, 이 식을 세운 순간부터 우리가 할 일은 1가지로 줄어들게 됩니다.

left = 1, right = K로 두고, left <= right일 때까지 while문을 진행하면서 위 식에 따라서 cnt를 계산한 후, cnt와 K를 비교하면서 left 혹은 right를 초기화하는 것입니다.