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

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[마구간 정하기]

 

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)가 한 줄에 하나씩 주어진다.

 

*출력 설명

첫 번째 줄에 가장 가까운 두 말의 최대 거리를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_25.txt', 'rt')

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)

# 출력 : 3

 

input_25.txt(입력)

5 3 
1
2
8 
4 
9

 

 

중요내용

1. 변수 mid는 가장 가까운 말의 거리를 의미한다.
2. 변수 cnt는 배치한 말의 수를 의미한다.
3. 변수 ep는 말을 배치한 위치를 의미한다.