N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다.
각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.
<내 답안>
def Count(length):
cnt = 1
p = 0
for i in range(1, n):
if li[i] - li[p] >= length:
cnt += 1
p = i
return cnt
n, c = map(int, input().split())
li = []
res = 0
for _ in range(n):
li.append(int(input()))
li.sort()
lt = 1
rt = max(li)
while lt <= rt:
mid = (lt+rt)//2
if Count(mid) >= c:
res = mid
lt = mid + 1
else:
rt = mid - 1
print(res)
문제 읽었을 때 이해가 되지 않아 해설 앞부분을 듣고 풀었다.
Count(mid)로 리턴된 값은 말의 수 이다.
c보다 크거나 같다면 당연히 c마리의 말을 넣을 수 있다. (만약 c보다 작다면 그것은 최대로 넣을 수 있는 말의 수라는 것이니 c마리를 넣을 수 없다.)
따라서 이분탐색에서 범위를 mid 위로 다시 정하면 된다.
Count 함수 내에서는 첫번째 마구간에 말 한 마리를 넣어두고 시작하는 것으로 하여 인덱스 0, 즉 p = 0를 가지고 풀었다.
<모범답안>
def Count(len):
cnt = 1
ep = Line[0]
for i in range(1, n):
if Line[i]-ep >= len:
cnt += 1
ep = Line[i]
return cnt
n, c = map(int, input().split())
Line = []
for _ in range(n):
tmp = int(input())
Line.append(tmp)
Line.sort()
lt = 1
rt = Line[n-1]
while lt <= rt:
mid = (lt+rt)//2
if Count(mid)>=c:
res = mid
lt = mid + 1
else:
rt = mid - 1
print(res)