백준 1300. K번째 수

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

1300번: K번째 수

 

배열의 크기 N이 최대 100000이고 N*N 배열이기 때문에 2차원 배열을 한번만 훑어도 시간초과가 날것이다.

즉 이말은 배열을 훑지 않고 k번째 수가 몇인지 알아내야 한다는 뜻이다.

left를 0, right를 최댓값인 n*n으로하고 이분탐색을 시작한다.

계산된 mid 값 보다 작거나 같은 값이 배열에 몇개 있는지 알아내야 하는데, 말했듯이 배열을 한번만 쭉 훑어도 이미 시간초과다. 배열을 훓지 않고 mid 보다 작은 값이 몇개 있는지 알아내야 한다.

 

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

위와 같이 4*4 배열이 있고 도출한 mid 값이 8이라고 하면, 8보다 작거나 같은 값이 몇개인지 알아내는 방법은 

각 행별로 계산해보면 된다. 

1행의 가장 큰 값은 1 * 4 = 4 일것이고, mid 값인 8보다 작거나 같으므로 1행에서 mid 값인 8보다 작거나 같은 숫자의 갯수는 4개, 즉 n개이다.

 

2행의 가장 큰 값은 2 * 4 = 8일것이고, mid 값인 8보다 작거나 같으므로 2행에서 mid 값인 8보다 작거나 같은 숫자의 갯수는 4개다.

 

3행의 가장 큰 값은 3 * 4 = 12일것이고, mid 값인 8보다 크다.

이때 3행에서 mid 값인 8보다 작거나 같은 값의 갯수는 8 / 3 = 2 즉 mid / 행 이다. 

 

 

이렇게 mid 값에 따라 mid 값 보다 작거나 같은 숫자의 갯수를 구하고, 

만약 mid 값 보다 작거나 같은 숫자의 갯수가 k 보다 작다면 해당 mid 값은 답이 될수가 없으므로 범위를 오른쪽으로 옮긴다.

 

k보다 크거나 같다면 mid 값은 정답이 될 가능성이 있으므로 정답을 갱신하고 범위를 왼쪽으로 옮겨서 범위를 좁혀나간다.