[백준 1300번] K번째 수

난이도: 골드 III

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

1300번: K번째 수

백준 1300번 문제 K번째 수

N의 최대 크기가 10만이므로, 배열에 들어갈 모든 수를 계산하기에도 벅찹니다 (10만 x 10만 번의 연산).

따라서 이 문제는 모든 숫자를 계산하지 않고 풀 수 있어야 합니다.

 

K번째 수를 구한다는 것은, 이보다 작은 수가 K-1개 존재한다는 뜻입니다.

이러한 상황에서 비교 연산을 훨씬 덜 하면서 원하는 수를 탐색하는 방법 중 하나로 이분 탐색이 있습니다.

이분 탐색에 대한 자세한 설명은 여기를 참고하시기 바랍니다.

 

이분 탐색에 필요한 두 변수 start, end를 둡니다. start = 1, end = K의 초기값을 가지고 시작합니다.

start <= end를 만족하는 동안, loop를 반복하며 다음을 수행합니다.

 

1. mid = (start + end) / 2로 합니다.
2. 각 행은 i*j의 값이 들어있습니다. 각 행 별로 mid보다 작은 숫자의 개수를 구하기 위해, i * j <= mid 부등식을 이용합니다.
   • 부등식을 재배열하면 j <= (mid / i)가 됩니다. 따라서 각 i에 대해 mid보다 작은 숫자가 (mid / i)개 존재합니다.
   • 단, 각 행에는 총 n개의 숫자가 있으므로, mid / i가 n을 넘어갈 것을 대비하여, min (mid/i, n)을 하도록 합니다.
   • 여기서 얻은 j값을 cnt 변수에 누적합니다.
3. cnt가 k보다 작은 경우, mid의 값을 늘려야 합니다. 따라서 start = mid + 1이 됩니다.
4. 그 외의 경우, mid의 값을 별도로 기록한 후, mid의 값을 줄이기 위해, end = mid - 1이 됩니다.

위 과정을 통해 얻은, 마지막으로 별도로 기록한 mid값이 정답이 됩니다.

 

 

채점 결과

전에 풀었을 땐 미처 완성하지 못하고 넘어갔었는데 오늘은 성공적으로 풀었네요.