[문제]
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
[풀이]
def Count(len): # 말이 들어있는 마구간 갯수
cnt = 1 # 말 한 마리 배치
ep = horses[0] # 첫번째 마구간에 말 배치
for i in range(1, n):
if horses[i]-ep >= len: # 마지막에 배치한 지점과 현재 배치하려고 하는 지점의 거리 len 보다 크면
cnt += 1 # 해당 위치에 말 배치 가능
ep = horses[i] # 마지막 말의 배치 지점을 바꿔줌
return cnt # 배치한 말의 마리 수를 리턴
n, c = map(int, input().split())
horses = []
res = 0
largest = 0
for _ in range(n):
tmp = int(input())
horses.append(tmp)
horses.sort()
lt = 1 # 두 말 사이의 거리가 가장 가까운 건 1
rt = horses[n-1]
while lt<=rt:
mid = (lt+rt)//2
if Count(mid) >= c: # mid: 가장 가까운 말들의 거리
res = mid
lt = mid + 1 # 가장 인접한 두 마리 말의 최대 거리이므로, 답이라면 그것보다 더 짧은 거리는 당연히 답이 가능하니 더 큰 거리를 찾아줘야함
else: # 답이 되지 않는다면, 가장 인접한 두 마리 말의 거리가 너무 긴 것이므로 원하는 c마리의 말을 배치하지 못함
rt = mid - 1 # 거리를 줄여줘야 하므로 더 긴 쪽은 답이 되지 않음
print(res)
[내용]
- Count 함수 구현이 이해되지 않아서 아예 접근 조차 하지 못했다..
= Count 함수는 말이 들어있는 마구간의 갯수를 리턴함. => Count 함수의 리턴값이 c보다 크거나 같다면 해당 거리가 가능하다는 뜻
- 무엇을 변수로 두어야 할 지에 대한 판단이 미흡했다. => 거리를 변수로!
= 가장 가까운 두 말의 최대 거리를 알아야 하므로 거리에 대해 범위를 정하면서 결과값을 알아야 함
= mid 값은 가장 가까운 말들의 거리를 의미함
<알고리즘 설명>
1, 2, 4, 8, 9
1) lt =1, rt=9 이고 1번말이 1 위치에 있을 때
- mid(가장 가까운 말들의 거리) = 5: 가장 가까운 두 말의 최대 거리. = 모든 말들의 거리는 5보다 크거나 같아야 한다!
- 2번말은 2에 있을 수 없음: 두 말의 거리가 2-1 > 5 이므로 2번말은 8의 위치에 있어야 함
- 3번말을 놓을수가 없음
2) 1)이 성립하지 않으므로 mid(가장 가까운 말들의 거리)를 줄여야 함. -> rt=4로 수정
'Coding Test > Python' 카테고리의 다른 글
| [python] 재귀함수를 이용한 이진수 출력 (0) | 2023.03.15 |
|---|---|
| [python] 가장 큰 수 (0) | 2023.02.26 |
| [Python] 뮤직비디오(결정알고리즘) (0) | 2023.02.16 |
| [python] 랜선자르기(결정알고리즘) (0) | 2023.02.13 |
| [python] 이분검색 (0) | 2023.02.13 |