파이썬 알고리즘 223번 | [백준 1300번] K번째 수 - 이분 탐색,매개 변수 탐색

223. K번째 수

1) 어떤 전략(알고리즘)으로 해결?

• 이이이분탐색

2) 코딩 설명

<내 풀이>

출처 (아이디어 및 코드) : https://claude-u.tistory.com/449

import sys
n = int(sys.stdin.readline().rstrip())
k = int(sys.stdin.readline().rstrip())
s,e = 1,k # 이렇게 범위를 잡았던 것이 이해가 안갔었는데!! 
# k번째 수라면 k 보다 항상 작기 마련, 
# 따라서 범위를 1부터 k로 잡은 것이지 
res = 100000000000
# A보다 작은 숫자가 몇개 ? => A//row (1,2,,,n)
while s<=e : 
    mid = (s+e)//2 
    tmp_total = 0 # mid 가 몇 번째 인지 알려주는 것 
    for i in range(1, n+1) : 
        tmp_total+= min(mid//i, n) 
        # 20//1 => 20이 될 수 없음 최대 n
    if tmp_total>=k : # 지금 찾은 mid 가 k번보다 크거나 같으면 
        res = mid
        e = mid-1
    
    else : s = mid+1 # mid 가 k번보다 작다면 더 높여야지 

print(res)

<내 틀렸던 풀이, 문제점>

1) 메모리 초과

import sys
n = int(sys.stdin.readline().rstrip())
k = int(sys.stdin.readline().rstrip())
blis = []
for i in range(1,n+1) : 
    for j in range(1,n+1) : 
        blis.append(i*j)
blis.sort()
print(blis[k])

<반성 점>

<배운 점>