https://www.acmicpc.net/problem/1477
내 풀이
n,m,l=map(int, input().split())
rest_area=list(map(int, input().split()))
rest_area.append(0)
rest_area.append(l)
rest_area.sort()
def count(len):
cnt=0
for i in range(1,n+2):
cnt+=(rest_area[i]-rest_area[i-1]-1)//len
return cnt
lt=1
rt=l
while lt<=rt:
mid=(lt+rt)//2
if count(mid)<=m:
res=mid
rt=mid-1
else:
lt=mid+1
print(res)
-함수 count 작성
휴게소 사이의 거리를 len으로 나누어서 만들 수 있는 휴게소의 개수를 도출하는 함수 작성
-->컴퓨터적으로 사고하여 함수 작성
:최대 거리의 최솟값을 도출하는 함수를 작성하는 것은 복잡하고 어려운 일이기에
최대 거리의 최솟값을 이분 검색을 활용해서 함수에 집어넣는 구조를 선택
물론 이 때의 함수는 해당 거리일 때 만들 수 있는 휴게소 개수
Boj 큐2 python (0) | 2021.07.23 |
---|---|
Boj 9012 괄호 python (0) | 2021.07.22 |
Boj 10828 스택 python (0) | 2021.07.19 |
Boj 3079 입국심사 python (0) | 2021.07.16 |
Boj 2512번 예산 python (0) | 2021.07.13 |
댓글 영역