728x90
반응형
문제 출처:
문제 풀이 :
- 앞서 본 이분탐색과 같은 문제이다.
- 이런 문제류에서 바뀌는 부분은 찾는 특정값을 비교할때 사용되는 결과값을 구하는 부분인데 여기서는 아마 gap을 구하는 부분만 신경 써주면 될 것이다.
- 보통 for문으로 구하니까 복잡하지 않은 이분탐색 문제에선 while문 안에 있는 for문을 신경써서 보면 문제가 쉽게 이해가 된다.
n, c = map(int, input().split())
house = []
for _ in range(n):
x = int(input())
house.append(x)
house.sort()
start = 1
end = house[-1] - house[0]
result = 0
while (start <= end):
mid = (start + end) // 2
old = house[0]
count = 1
for i in range(1, len(house)):
if house[i] >= old + mid:
count += 1
old = house[i]
if count >= c:
start = mid + 1
result = mid
else:
end = mid - 1
print(result)
반응형
'Computer Science > Algorithm' 카테고리의 다른 글
[백준] 21609 - 상어 중학교 (Python) (0) | 2021.05.10 |
---|---|
[백준] 21608 - 상어 초등학교 (Python) (0) | 2021.05.10 |
[백준] 11286 - 절대값 힙 (Python) (0) | 2021.04.09 |
[백준] 2512 - 예산 (Python) (0) | 2021.04.09 |
[백준] 최대,최소 힙 (Python) (0) | 2021.04.09 |