4.4 마구간 정하기 (결정 알고리즘)

문제

마구간 정하기(결정알고리즘)

N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마
구간간에 좌표가 중복되는 일은 없습니다.
현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다.
각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을
마구간에 배치하고 싶습니다.
C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대
값을 출력하는 프로그램을 작성하세요.
▣ 입력설명
첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 한 줄에 하나씩
주어집니다.

▣ 출력설명
첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.

▣ 입력예제 1
5 3
1
2
8
4
9

▣ 출력예제 1
3

내 풀이

n, c =map(int, input().split())
position_list=[]
result_list=[]

def position(length):
    for j in position_list:
        if position_list[0]<=j-length and j+length<=position_list[len(position_list)]:
            result_list.append(j)
    return result_list
            
for i in range(n):
    p=int(input())
    position_list.append(p)

position_list.sort() 

lt=1
rt=max(position_list)

while lt<=rt:
    mid=(lt+rt)//2
    if len(position(mid))>0:
        res=mid
        lt=mid+1
    else:
        rt=mid-1

-무엇을 변수로 두어야 할 지에 대한 판단이 미흡했음

거리를 변수로 두어야 함!

why? 가장 가까운 두 말의 최대 거리를 알아야 하므로 거리에 대해 범위를 정하면서 결과값을 도출해야 함

 

-코드 구현 능력 부족

mid를 최소 거리로 설정해서 계산했을 때 성립 여부를 함수로 작성하지 못했음

---

강의 풀이

def count(len):
    cnt=1
    ep=Line[0]
    for i in range(1,n):
        if Line[i]-ep>=len:
            cnt+=1
            ep=Line[i]

n, c=map(int, input().split())
Line=[]

for p 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)

-함수 작성 능력 중요

def count(len):
    cnt=1
    ep=Line[0]
    for i in range(1,n):
        if Line[i]-ep>=len:
            cnt+=1
            ep=Line[i]

count 함수는 말이 들어있는 마구간의 개수를 나타내는 함수이다.

따라서 count 함수 도출값이 c보다 크거나 같다면 해당 거리가 가능한 값이다

 

하지만 우리는 가능한 값을 찾는 것이 목적이 아니라 가능한 값 중에서 최대를 찾으므로 범위를

다시 조정하여 위 함수를 돌려본다