[백준] 2110 : 공유기 설치

letsbebrave·2022년 4월 8일

codingtest

목록 보기

80/146

문제

메모리 초과 풀이

import sys
import itertools

n, s = map(int, sys.stdin.readline().split())
m = []
for i in range(n):
    m.append(int(sys.stdin.readline()))

m = sorted(m, reverse = True)
m = list(itertools.combinations(m, s))    
result = []

minus = [[0 for j in range(len(m[0])-1)] for i in range(len(m))] # 이차원 배열 선언

for i in range(len(m)):
    for j in range(len(m[i])-1):
        minus[i][j] = m[i][j]-m[i][j+1]

for i in range(len(minus)):
    result.append(min(minus[i]))

print(max(result))

막힌 부분

사고의 흐름

일단 이진탐색을 써야 하는 것은 알겠는데, 이게 n개를 선택해야 하는 카드 놓기 문제와 비슷한 측면이 있어서

(공유기 놓을 n개의 마을을 뽑기) by 재귀 & 이분탐색
(거리 사이의 최댓값 구하기)

무언가 이렇게 되는 구조인 것 같은데, 이분탐색을 어느 방식으로 써야하는지를 모르겠다. 이분 탐색이라는 것이 리스트의 원소 중 어떤 특정 원소를 찾기 위해 진행하는 것인데, 이 경우엔 원소를 찾는 게 목적이 아니라 두 공유기 사이의 최대 거리를 출력하는 게 목적이기 때문에 이분탐색을 어디에 어떻게 써야 맞을지 모르겠다.

이진탐색을 진행하는 대상

두 공유기 사이의 거리를 기준으로 이진탐색을 진행해줘야 함!

공유기 사이의 최소 거리가 2일 때

1에 설치 -> 1+2 3 이상인 좌표
2에 설치 X
4에 설치 -> 4+2 6 이상인 좌표
8에 설치 -> 8+2 10 이상인 좌표
9에 설치 X

총 3군데 설치 가능!

but 공유기 사이의 최소 거리가 4일 경우
1에 설치 -> 1+4 5 이상인 좌표
2에 설치 X
4에 설치 X
8에 설치 -> 8+4 12 이상인 좌표
9에 설치 X

총 2군데 설치 가능!

따라서, 공유기 설치 가능한 곳의 개수를 구하고
원하는 공유기 수보다 크면 -> 거리를 늘려줌
원하는 공유기 수보다 작으면 -> 거리를 좁혀줌

by 이진탐색.

정리하면, 거리를 기준으로 파악해야 한다는 게 중요하다!!

정답

mid는 두 공유기 사이의 거리
cur은 현재 위치 파악을 위해 쓰는 변수
tmp에 한 번 설치한 공유기들 중 최소 거리가 들어있음
그리고 ans에 그동안 설치한 모든 공유기의 최소 거리들 중 max 값들을 구해주는 것

import sys

n, s = map(int, sys.stdin.readline().split())
m = []
for i in range(n):
    m.append(int(sys.stdin.readline()))

def bsearch(m, s):
    m.sort()
    start = 0
    end = m[-1] - m[0] # 두 집 사이의 거리 중 최댓값
    ans = 0
    
    while start <= end:
        mid = (start + end) // 2
        count = 1
        cur = m[0]
        tmp = float('inf')
        
        for i in range(1, len(m)):
            if cur + mid <= m[i]: # 내가 놓을 수 있는지 알아보기
                tmp = min(m[i]-cur, tmp) # 거리 중 최솟값을 구하기 위해 비교
                count += 1
                cur = m[i]
        
        if count < s: # 공유기 설치 더해야 => 간격 더 짧게 해야
            end = mid - 1
        elif count >= s: # 공유기 설치 완료 or 더 많이 됨 => 간격 더 길게 해야
            start = mid + 1
            ans = max(ans, tmp)
            
    return ans

print(bsearch(m, s))

22.04.12 다시 풀어보기

import sys

N, C = map(int, sys.stdin.readline().split())
house = sorted([int(sys.stdin.readline()) for i in range(N)]) # 정렬해서 오름차순으로 넣어줌

def sol(target):
    start = 0 # 두 공유기 간 최소 거리는 0
    end = house[-1] - house[0] # 두 공유기 간 최대 거리는 가장 멀리 있는 집에서 가장 가까이 있는 집의 차
    
    while start <= end:
        mid = (start + end) // 2 # 공유기 간 최소 거리
        count = 1 # 공유기 설치 대수
        cur = house[0] + mid # 현재 위치
        
        # 최소거리 mid에 따라 몇 개의 공유기를 설치할 수 있는지 count해주는 반복문
        for i in range(1, N):
            if cur <= house[i]:
                count += 1
                cur = house[i] + mid
        # 세어준 공유기가 target 보다 크면 => 거리가 늘어나야 함       
        if count >= target:
            start = mid + 1
            answer = mid
        # 세어준 공유기가 target 보다 작으면 => 거리가 작아져야 함    
        elif count < target:
            end = mid - 1
            
    return answer
           

print(sol(C))

22.05.10 다시 풀어보기

import sys
input = sys.stdin.readline

n, c = map(int, input().split())
houses = []
for _ in range(n):
    houses.append(int(input()))
houses.sort()

def binary_search(target):
    start = 0                   # 가장 인접한 거리의 최소 거리
    end = houses[-1]-houses[0]  # 가장 인접한 거리의 최대 거리
    res = 0

    while start <= end:
        cnt = 1
        crt = houses[0]
        width = (start + end) // 2 # 가장 인접한 거리
        
        for i in range(1, n):
            if crt + width <= houses[i]: # 공유기를 놓을 수 있으면
                cnt += 1
                crt = houses[i] # 어차피 width는 가장 인접한 거리이므로 갱신해줄 필요 없음!
        
        if cnt < c:
            end = width - 1
        else:
            start = width + 1
            res = width
    
    return res

print(binary_search(c))