백준 1300: K번째 수 (Python)

 

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

1300번: K번째 수

 

알고리즘 자체는 쉬우나 문제 풀이를 이해하는 과정이 너무 어려웠다

그래서 일주일 전 쯤에 풀다가 그 상태로 방치하고 오늘 다시 함..ㅋㅋㅋ

2차원 배열 -> 1차원 배열로 바꾸는 비효율적인 방법밖에 생각이 나질 않아서

다른 사람들 풀이 참고해서 풀었는데 그마저도 이해가 안 가서 오랫동안 끙끙 앓았다ㅠ

 

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

start = 1
end = k

while start <= end:
    mid = (start + end) // 2
    cnt = 0

    for i in range(1, n+1):
        cnt += min(mid//i, n)

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

print(start)

 

 

k번째 수를 찾으려면 k보다 작은 수가 몇 개인지 찾아야 한다는 것을 이해하고

직접 알고리즘 따라 풀어보면(^^....) 이해가 된다.