[백준 2024/03/27] 1300번 K번째 수

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

1300번: K번째 수

 

1. 접근 방법

이 문제 처음에 이상하게 접근하다가, 다시 이진 탐색으로 돌아온 문제이다.

이후 답을 구글에서 알아보았다.

 

이해를 한 것을 적어보자면, 

 

1  2  3

2  4  6

3  6  9

 

이렇게 값이 있다면, 

start 값을 1, end 값을 9로 설정한다.

이후 mid 값을 (start + end)//2를 통해서 한 후, 5보다 작은 값을 계산을 해준다.

 

이 계산을 해주는 방식이 특이하다.

색깔로 칠해진 열들로 보게 되면, 

mid//i를 한다.

즉, 색깔의 밑에는 모두 i의 배수일 것이다.

보라색을 예로 들면 보라색은 2의 배수가된다. 2*2 가 되고, 2*3 이 된다.

또한 2로 나누어주게 되면 또 1, 2, 3의 값을 가지게 된다.

이에 대해서 mid도 같이 // 2를 해주면, 2.xxx 이므로 2가 나오게 되고, 따라서 min( mid//2, 3)을 통해서, 2를 cnt에 더하게 되면

그 값이 해당 column에 대해서 5보다 작은 값들의 개수가 될 것이다. 

 

즉 5보다 작은 수 2, 4를 cnt로 넣어주는 것과 같은 원리이다.

이렇게 5보다 작은 수들을 다 계산을 하게 되고, cnt에 넣어준다.

 

만약 cnt가 k보다 작게 되면, mid 값을 높여야지 더 많은 수들을 cnt할 수 있을 것이다.

이 땐 높여주고, 그 반대면 mid값을 낮춰준다.

 

이 때, 등호는 크거나 같다로 들어가게 된다. 왜냐하면, 5는 애초부터 이 배열에 들어가 있는 수가 아니고, 따라서 우리가 구해야하는 수는 해당 배열에 포함된 수면서, cnt가 k인 가장 작은 값을 찾아줘야 하기 때문에, mid를 낮춰주는 것이다.

 

2. 코드

n = int(input())
k = int(input())

start = 1
end = n ** 2
result = 0
while start <= end:
    mid = (start + end) // 2
    cnt = 0
    for i in range(1, n + 1, 1):
        cnt += min(mid // i, n)

    if cnt >= k:
        result = mid
        end = mid - 1
    else:
        start = mid + 1

print(result)