[알고리즘] 백준1300 K번째 수 - 파이썬

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

1300번: K번째 수

 

 

[첫 번째 실패 코드]

from sys import stdin

n = int(stdin.readline())
k = int(stdin.readline())

b_list = [(i+1) * (j+1) for i in range(n) for j in range(n)]

b_list.sort()
print(b_list)

- 단계별풀어보기의 '이분 탐색' 파트인데 이렇게 풀면 되는 거 아닌가 싶었다.. 소제목부터가 

의외로 이분 탐색으로 풀었어야 했나보다..ㅋㅋ 실패한 코드처럼 제출하면 '메모리 초과'가 뜨는데 이중 포문에다 정렬까지 해서 너무 비효율적이긴 했다.

 

 

[두 번째 성공 코드]

- 도저히 어떻게 이분 탐색으로 풀어야 될지 감이 안 잡혀서 결국 다른 분의 블로그 참조.. 이게 몇 번째 인지 현타가 온다ㅜ

https://hongcoding.tistory.com/m/13

[백준] 1300번 K번째 수 (Python 파이썬)

from sys import stdin

n = int(stdin.readline())
k = int(stdin.readline())

start, end = 1, 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:
        result = mid
        end = mid - 1
    else:
        start = mid + 1

print(result)

- 역시나 이분탐색문제는 end를 어떤 수로 선언하는지와 while문안에 for문 부분이 중요한 것 같다.

- 심지어 이 코드도 잘이해가 되지 않아서 손 버깅을 하고 나서야 이해가 갔다. 이분 탐색 파트는 연습이 많이 필요한 것 같다..