1300번 K번째 수(이분탐색) - ☆

#문제링크 : https://www.acmicpc.net/problem/1300

<전략>

1. 블로그를 참고했습니다.

2. 어떤 수 mid에 대하여 mid보다 작거나 같은 수를 세는 방법이 있다. A는 A[i][j] = i*j 이므로, i행의 원소값은 전부 i의 배수일 수 밖에 없다. 즉, i행은 i*1, i*2, i*3 ... i*j 로 이루어져 있다. 만약 mid가 i*3 < mid < i*4라 해보자. i행에서 mid보다 작거나 같은 수는 mid/i 개다. 이유는, i*1, i*2, i*3 총 3개고, 위의 부등식을 i로 양변을 나누어 주면,

3 < mid/i < 4가 되어, mid/i = 3.xxx = 3(소수점을 버리면) 이기 때문.

만약 i*3 == mid < i*4 라 해도, mid보다 작거나 같은 수는 3으로 동일하다.

자, 여기서 중요하게 짚고 넘어가야할 사실이 있다. 만약 i가 1이라면 어떨까?
i가 1이고, n이 5라고 해보자. A배열은 5X5배열이고, mid 값을 9라 하면, 위의 방식대로 mid/i 연산을 했을 때, 값이 어떻게 나오는가? 바로 mid / i = 9 / 1 = 9가 나온다. 이걸 해석하면 1번째 행에서 mid보다 작거나 같은 값은 9개가 있다는 소리이다. 하지만 이건 모순이다. 왜냐하면 A배열은 분명 5X5배열이라, 하나의 행에 최대 5개의 열이 있기 때문이다. 즉, mid/i 값이 n값보다 커질 경우엔 n값을 i행에서 mid보다 작거나 같은 요소의 갯수로 사용하면 된다.

결론은, i행에서 mid보다 작거나 같은 요소의 갯수는 min(mid/i, n) 이 된다.

3. 이제, 임의의 mid값을 선정하여, mid값보다 작은 요소의 갯수를 행별로 구해주어 다 더한 후 그 값이 k보다 작냐 크냐로 다시 mid값을 선정해주면 된다. 즉, mid값을 선정할때, 이분탐색으로 선정한다.

※주의사항

1. mid값보다 작거나 같은 요소의 갯수를 세어주므로 count가 k값보다 크거나 같은 경우와 k값보다 작은 경우로 나누어주어야 한다. 무슨 말이냐하면, 1 2 2 3 3 3 4 4 라는 배열이 있을때, mid값이 3이라 하자. 그럼 mid값보다 작거나 같은 요소의 갯수는 총 6개(count)다. 3을 포함하기 때문에 6개(count)가 된다. 이 count=6 가 의미하는 것은 k가 4, 5, 6 인 경우를 모두 아우른다. k가 4번째건, 5번째건, 6번째건, 정답은 3이기 때문이다. 한마디로, count값은 구하려는 k번째 값(여기선 3)의 최대 인덱스이므로, 3의 인덱스 4, 5, 6 중 6이 count값이 된다. 그래서, count가 k값보다 크거나 같은 경우가 동일한 정답을 가지게 되는 것이다.

2. mid값이 start==end가 될때까지 수렴하고, start==end==mid가 되는 시점에 무조건 count>=k 이므로, end = mid - 1이 되어버린다. 이후에 end<start==mid이 돼서 while문을 빠져 나가므로, 정답은 start나 mid가 되어야 한다.

Code