[BOJ] 백준 1300 K번째 수

태환·2024년 1월 31일
0

Coding Test

목록 보기
34/151
post-custom-banner

📌 [BOJ] 백준 1300 K번째 수

📖 문제

📖 예제

📖 풀이

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):
    cnt += min(mid//i, N)
  if cnt < k:
    start = mid + 1
  else:
    end = mid - 1
    result = mid
print(result)

본 문제는 이진 탐색의 전형적인 코드 모습을 보이지만, 각 행마다 (mid // i) 개수 만큼의 작은 수를 갖는다는 생각을 떠올리기는 어려운 문제이다.

profile
연세대학교 컴퓨터과학과 석사 과정
post-custom-banner

0개의 댓글