[파이썬][백준 1300][💛골드 3] K 번째 수 (파라메트릭 서치)

🧞‍♂️‍ 난이도

💛 골드 3

🧞‍♂️ 문제

K 번째 수

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

🧞‍♂️ 내 풀이

이 문제는 파라메트릭 서치로 안풀면 메모리 제약을 통과할 수 없을것 같다. 처음에는 아무생각없이 뜬금없는 bfs로 풀고 메모리 제약을 나중에 봤다.

그럼 파라메트릭 서치으로는 어떻게 풀어야할까.

파라메트릭 서치 는 보통 특정 조건 이 만족 안될때까지 범위를 좁혀서 최적해를 찾는데 이 문제에서는 mid 보다 앞쪽에 있는 숫자의 개수가 K 보다 작을때까지 범위를 좁히는 것이다.

쉽게 말해서, mid는 잠재적인 정답의 후보가 되는것이고, mid앞에 있는 숫자들이 몇개있는지를 구해서 K 위치가 되도록 탐색하는 것이다.

알고리즘

1. mid를 구한다
2. mid보다 앞에 있는 숫자의 개수를 구한다
3. mid보다 앞에 있는 숫자의 개수와 K 를 비교해서 유효한 범위인지 파악한다.
   • 유효한 범위이면 answer를 mid로 설정하고 알맞게 범위를 좁힌다. 여기서 유효한 범위는 mid보다 앞에 있는 숫자가 K보다 크거나 같을때를 말한다.

여기서 2. 가 어려운건데 mid를 구할때마다, 1 ~ N 까지의 숫자로 한 번씩 mid 를 나눈 모든 몫을 더한다.

temp = 0
for i in range(1, N + 1):
    temp += min(mid//i, N)

그럼 여기서 temp는 잠재적으로 K위치에 해당되는 mid 값보다 앞에 있는 숫자들의 개수이다. 만약에 temp가 K보다 작다면, mid를 오르쪽으로 더 이동시켜봐야하는거고, temp가 K보다 크거나 같으면, 일단 정답이 될 수 있으니까 answer에 저장을 하고, mid의 범위를 왼쪽으로 이동시켜보는 것이다.

그러면 자연스럽게 마지막에 저장될 mid가 정답이 되는 것이다.

🧞‍♂️ 파이썬 코드

import sys
input = sys.stdin.readline

N = int(input())
K = int(input())

answer = 0
left, right = 1, K
while left <= right:
    mid = left + (right - left) // 2
    temp = 0
    for i in range(1, N + 1):
        temp += min(mid//i, N)
    if temp >= K:
        answer = mid
        right = mid - 1
    else:
        left = mid + 1
print(answer)

---

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기