백준 22868 산책 (small) Python

🐸 문제 정보

22868번: 산책 (small)

 

🤖 알고리즘

이분탐색

 

⏱️ 풀이 시간

26.22m

 

📝 풀이

문제를 보고 이분탐색으로 풀어야된다는 것은 알았으나... 정확한 아이디어가 떠오르지 않아 검색의 힘을 빌렸다.

처음에는 mid와 근사한 값에 공유기를 위치시키는 형태로 이분탐색을 생각했었는데,

그게 아니라 mid는 두 집 사이의 거리로 두고, 그 거리만큼 공유기를 두었을 때 비치할 수 있는 공유기의 개수로 정답을 파악하는 형식이었다.

이때 start와 end의 값을 평소처럼 0번째 인덱스와 마지막 인덱스로 두는 바람에 계속 실패했는데,

이 문제에서는 인덱스보다 사이의 거리가 어느정도인지가 더 중요하기 때문에

start는 1, end는 첫번째 인덱스 ~ 마지막 인덱스의 차이로 두고 푸는 것이 맞다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n, c = list(map(int, input().rstrip().split()))
home = sorted(int(input().rstrip()) for _ in range(n))
start, end = 1, home[-1] - home[0]
res = 0

while start <= end:
    mid = (start + end) // 2
    prev, temp = home[0], 1
    for cur in home[1:]:
        if mid <= (cur - prev):
            prev = cur
            temp += 1
    if temp >= c:
        start = mid + 1
        res = mid
    else:
        end = mid - 1

print(res)