📌문제
https://www.acmicpc.net/problem/2110
🎖️난이도
✔️풀이
# sol1) sys.stdin.realine(), 이분탐색 => 664ms
import sys
n, c = map(int, input().split())
x_list = sorted([int(sys.stdin.readline()) for _ in range(n)])
start = 1 # 최소 거리
end = x_list[-1] - x_list[0] # 최대 거리
result = 0 # 인접(최소) 공유기 사이의 최대 거리
# start~end 사이에서 "인접 공유기 사이 거리(mid)" 바꿔가며 이진탐색
# 즉, 변수 : "거리" !
while(start <= end):
mid = (start + end) // 2 # 평균(중간) 거리부터 탐색 시작
tmp_x = x_list[0]
cnt = 1 # 첫번째 집에 미리 설치했으므로
# 인접 공유기 사이 (최소) 거리 이상이면 공유기 모두 설치
for i in range(1, n):
if x_list[i] >= tmp_x + mid:
tmp_x = x_list[i]
cnt += 1 # 공유기 설치 개수 추가
# 인접 공유기 사이 거리 늘리기 (더 넓게 설치)
if cnt >= c:
result = mid
start = mid + 1
# 인접 공유기 사이 거리 줄이기 (더 좁게 설치)
else:
end = mid - 1
print(result)
# sol2) sys.stdin.realine(), 이분탐색(최대 범위 // c-1) => 384ms
import sys
n, c = map(int, input().split())
x_list = sorted([int(sys.stdin.readline()) for _ in range(n)])
start = 1 # 최소 거리
end = (x_list[-1] - x_list[0]) // (c-1) # 최대 거리 (c-1로 나누기!)
result = 0 # 인접(최소) 공유기 사이의 최대 거리
# start~end 사이에서 "인접 공유기 사이 거리(mid)" 바꿔가며 이진탐색
# 즉, 변수 : "거리" !
while(start <= end):
mid = (start + end) // 2 # 평균(중간) 거리부터 탐색 시작
tmp_x = x_list[0]
cnt = 1 # 첫번째 집에 미리 설치했으므로
# 인접 공유기 사이 (최소) 거리 이상이면 공유기 모두 설치
for i in range(1, n):
if x_list[i] >= tmp_x + mid:
tmp_x = x_list[i]
cnt += 1 # 공유기 설치 개수 추가
# 인접 공유기 사이 거리 늘리기 (더 넓게 설치)
if cnt >= c:
result = mid
start = mid + 1
# 인접 공유기 사이 거리 줄이기 (더 좁게 설치)
else:
end = mid - 1
print(result)
# 오답 (시간초과 : input(), 이분탐색)
n, c = map(int, input().split())
x_list = sorted([int(input()) for _ in range(n)])
start = 1 # 최소 거리
end = x_list[-1] - x_list[0] # 최대 거리
result = 0 # 인접(최소) 공유기 사이의 최대 거리
# start~end 사이에서 "인접 공유기 사이 거리(mid)" 바꿔가며 이진탐색
while(start <= end):
mid = (start + end) // 2 # 평균(중간) 거리부터 탐색 시작
tmp_x = x_list[0]
cnt = 1 # 첫번째 집에 미리 설치했으므로
# 인접 공유기 사이 (최소) 거리 이상이면 공유기 모두 설치
for i in range(1, n):
if x_list[i] >= tmp_x + mid:
tmp_x = x_list[i]
cnt += 1 # 공유기 설치 개수 추가
# 인접 공유기 사이 거리 늘리기 (더 넓게 설치)
if cnt >= c:
result = mid
start = mid + 1
# 인접 공유기 사이 거리 줄이기 (더 좁게 설치)
else:
end = mid - 1
print(result)
# 오답 (시간초과 : 범위가 크므로 완전 탐색은 x)
import sys
from itertools import combinations
n, c = map(int, input().split())
x_list = sorted([int(input()) for _ in range(n)])
result = 0 # 인접 공유기 사이의 최대 거리
for comb in combinations(x_list, c):
if (comb[0], comb[-1]) == (x_list[0], x_list[-1]):
comb_min_dist = comb[1] - comb[0] # 1
if comb_min_dist < result:
continue
for i in range(1, c-1):
tmp_dist = comb[i+1] - comb[i]
if tmp_dist < result:
break
result = min(tmp_dist, comb_min_dist)
print(result)
🌞참고
[input() vs sys.stdin.readline()]
jupyter에서는 input() 밖에 사용 불가하지만, 실제로는 sys.stdin.readline()이 훨씬 빠름!
input()으로 하면 시간초과 나는 경우가 있음
'[ 알고리즘 ] > Sort & Binary Search' 카테고리의 다른 글
[백준] 1300. K번째 수 (0) | 2022.06.30 |
---|---|
[백준] 10816. 숫자 카드 2 (0) | 2022.06.30 |
[프로그래머스] 입국심사 (0) | 2022.06.29 |
[프로그래머스] 가장 큰 수 (0) | 2022.06.29 |
[프로그래머스] K번째수 (0) | 2022.06.29 |