[BOJ][1300번] K번째 수

안녕하세요 Dibrary입니다. 이번에는 이분탐색을 사용해야 풀 수 있는 문제를 정리해보겠습니다.

저에게 이 문제는 처음에 이해하는데 굉장히 시간이 오래 걸린 문제여서.... 정리를 꼭 해둬야겠다 생각했죠.

1300번: K번째 수

 

---

먼저 문제를 보고 어떤 방법으로 이분탐색을 해야 하는지 감을 잡지 못했습니다.
정확히는 '다른 풀이를 보고서도 이해가 안되었다' 가 더 맞는 표현같네요.

지금은 다른 풀이를 이해한 부분만 정리해보면 아래와 같습니다.

 

1. 대부분 start = 1로 잡고, (문제에서 시작 인덱스가 1이라고 했죠) end 를 k로 잡습니다. 여기서 end를 k로 잡는 이유는 n은 반드시 1보다 큰데 그 말은 k번째 숫자는 k보다 클 수가 없다는 것이죠.

예를 들어 n이 1이면 k번째 숫자는 k가 됩니다.
n이 2라도 되면 k번째 숫자는 반드시 k보다 작습니다. (더 정확히는 작거나 같죠)

 

2. 그리고 mid값보다 작은 것의 갯수를 한 방에 세는 것이 중요합니다. 당연히 mid값은 (start+end)//2로 하겠죠. 이정도는 이분탐색을 공부하면 간단히 알 수 있습니다. 문제는, 이 mid값을 가지고 '어디에 써먹느냐'가 문제죠.

다른사람들의 수식 대부분은 아래와 같습니다.

제일먼저 보이는건, for문으로 n번째 숫자까지를 진행합니다. 왜일까요? 문제에서 n*n크기의 배열이라고 했으므로, 숫자는 n까지 있기 때문에 for문으로 n번째까지 진행하는 것입니다.

그 다음에 문제는 min(int(mid/i), n) 입니다. 다르게 int를 줄여서 min(mid//i, n)으로도 나타낼 수 있죠.

이게 가장 이해가 안 되었던 코드 부분인데 나름 설명해보자면, 예제 1번을 빗대어서 설명해보겠습니다.

3*3 배열이므로 아래와 같은 값으로 구성될 겁니다.

자 그럼, mid값은 (1+7)//2 인 4가 되겠네요. 위 코드대로 진행하면 cnt는 

1. i가 1일때 3이 더해집니다.
2. i가 2일때 2가 더해집니다.
3. i가 3일때 1이 더해집니다. 

뭔가 감이 잡히시나요? 우선 i가 1일때 mid//i값은 4입니다. 그러나, 우리가 처음 문제에서 주어진 배열은 n행까지만 가능하므로 4는 n=3값보다 크죠. 그래서 min으로 n값이 cnt에 더해지는 것입니다.

i가 2일때 mid//i값은 2가 됩니다. 잘 보면 2행에서 4와 같거나 작은 값의 갯수는? 2개 입니다. 우연의 일치일까요?

i가 3일때 mid//i값은 1이 됩니다. 잘 보면 3행에서 4보다 작거나 같은 값의 갯수는 1개 입니다. 아하!

 

mid//i값은 각 i값에서 mid값보다 작거나 같은 숫자의 갯수를 의미하는구나! 를 알 수 있습니다.

그래서 이 갯수에 대해서 '이진탐색'을 진행하는 것입니다.

 

최종 코드는 아래와 같습니다.

 

생각보다 코드는 간단했는데, 이해하는데 꽤나 시간이 걸린 문제입니다.