[백준알고리즘] 1300번: K번째 수 -Python

[백준알고리즘] 1300번: K번째 수 -Python

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

1300번: K번째 수

너무 어려웠다....

아이디어가 도무지 기억이 안 나서 알고리즘 분류를 봤는데도 도저히 이분 탐색으로 할 수 있는 방법이 생각나지 않았다. 생각한 방법은 너무 시간이 오래 걸리는 것뿐이었다.

 

그래서 결국 여러 블로그들을 찾아봤다. 다 같은 내용인데 다 이해가 안돼서 아래의 블로그를 집중해서 보면서 직접 입력 예제를 손으로 따라서 계산하면서 이해했다.... 어려워 ㅜㅜ

https://developmentdiary.tistory.com/354

 

이해한 내용을 간단하게 아래의 코드와 함께 정리를 하겠다.

 

여기서 m은 B리스트를 일렬로 나열했을 때 cnt번째 값을 나타낸다.

즉, 주어진 행렬 A에서 m보다 작은 값의 갯수가 cnt개인 것이다.

 

cnt를 구하는 과정은 각 행에서 i번째 행에서 min(n, m//i) 값을 더해주는 것이다.

i번째 행에 있는 값은 모두 i*j로 이루어진 i의 배수들이고, i번째 행의 최댓값은 i*n이다. 따라서 i번째 행에서 m보다 작은 값의 개수는 m//i나 n이 된다.

m//i는 i * (m//i)를 한다고 생각해보면 이해할 수 있을 것이다. 갯수가 m//i나 n이 되는 것이며 m보다 작거나 같은 최댓값은 i * (m//i)나 i * n이 되는 것이다.

 

그렇게 행렬에서 m보다 작은 값들의 갯수를 구해주면 k번째 수인지 확인이 가능하다.

다만 위의 블로그에서도 언급해주었듯이 m보다 작거나 같은 값들의 개수를 구하고, 그 값들의 최소를 구해주면 되기 때문에 lower bound 방식처럼?? 가능한 수 중의 최소 값을 구해주었다.

n = int(input())
k = int(input())
s, e = 1, k
while s <= e:
    m = (s+e)//2
    cnt = 0
    for i in range(1, n+1):
        cnt += min(n, m//i)
    
    if cnt < k:
        s = m+1
    else:
        e = m-1
print(s)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다