[Java] 백준 1300 K번째 수

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

1300번: K번째 수

접근방법

이분탐색이라고 생각을 바로 하지는 못했다.

처음에는 k번째 인덱스 i,j를 구해서 값을 바로 출력해주는 방식을 생각했다

n = 3, k = 7 일때

하지만 A배열, B배열로 나뉘고 각 인덱스는 1부터 시작하고 B배열은 값을 정렬하기 때문에 바로 인덱스를 구한다는 생각은 틀린 생각이었다. 왜냐하면 이미 섞여있는상태에서 인덱스를 구한다는것은 말이 되지 않기 때문이다.

 

두 번째 방법으로는 n=3부터 n = 6 배열을 그리며 이해하면서 찾은 규칙을 활용 해 이분탐색을 사용해 풀게 되었다.

n=3일때

k가 7로 주어지고 n이 3으로 주어질때 표안 값은 순서를 나타낸다

그림을 보면 5일때 각 행을 돌며 5보다 작은 순서 값을 체크한다 

총 체크된 값의 합은 6이다 이규칙을 통해서 시작부분은 몰라도 6번 까지는 같은 값이라고 유추했고

이 부분에서  합이 6이고 처음시작하는 부분을 찾아내는데 이분탐색이 필요했다 

 

n=3 k=7

이분탐색을 진행해서 값이 K보다 클때마다 mid값이 배열의 값이 된다

최종 이분탐색을 마쳤을떄 왼쪽 우측이 겹쳤을때 까지 확인해서 

K보다 크거가 같은 값을 구하고 그때의 mid값을 저장하고 출력

또한 이분탐색의 끝을 k로 한 이유는 배열의 값은 k와 같거나 작기 때문에 생각하지 않아도 된다고 판단함

 

 

느낀점

이분탐색문제는 코드자체는 어렵지 않지만 어디에 어떻게 적용시키는가가 매번 어려운거 같다

k값이 최대 10의 9승 까지 들어오는데 이부분은 long으로 잡아야 하나 고민을 했는데

int의 최대값은 2의 31승 -1 값이니  2의 10승을 10의 3승과 유사하다고 생각하면 int로 잡아도 된다고 판단했다. 

 

import java.io.*;
public class boj1300 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(in.readLine());
		int k = Integer.parseInt(in.readLine());
		int left=1,right=k;
		int mid;
		int check;
		int result = 0;
		while(left <= right) {
			mid = (left+right)/2;
			check =0;
			for(int i=1;i<=n;i++) check += Math.min(n, mid/i);
			if(check >= k) {
				right = mid -1;
				result = mid;
			}else{
				left = mid +1;
			}
		}
		System.out.println(result);
	}
}