백준 : 2110 공유기 설치

백준 : 2110 공유기 설치

백준의 2805 나무 자르기 문제와 동일하게 이진탐색을 이용하여 풀이하였고, 함수의 동작도 동일했다. 만약 나무자르기 문제 풀이를 완료했다면 동일한 로직으로 푸는데 크게 어려움이 없을것이라 예상된다.

문제 이해

이 문제는 문제의 요구사항을 이해하는게 관건이다. 문제 정의가 명확하지 않다면, 삽질을 할 가능성이 크다.

N으로 주어진 집의 개수에 따라, C개의 공유기를 설치할 수 있는 최대 거리 중 각 공유기의 최소 거리를 구해야 한다. 요구 사항은 최소 거리를 리턴하는 것으로 정답은 하나만 있지만, 그 정답에 도달하는 방식은 여러개일 수 있다.

즉 최소 거리는 동일하지만, 어떤 집에 설치할지는 다양할 수 있다. 주어진 집 간의 거리를 예시로 들어보자면,

집의 좌표 : 1, 2, 8, 4, 9

최소 거리로 주어진 답은 3

공유기를 1, 4, 8 에 설치할때의 공유기 간 거리는 3, 4

공유기를 1, 4, 9 에 설치할때의 공유기 간 거리는 3, 5

둘 다 최소 거리는 3으로 동일하다. 이 점을 유의하면 문제를 접근하기 쉬워진다.

변수 설정

N : 집의 개수

C : 공유기의 개수

hh : 집 간의 좌표 → sort하여 최종 리스트는 h

최종 코드

import sys

def gongugi(left, right, target):
    best = 0
    while left <= right :
        mid = (left + right) // 2
        count = 1
        last_install = h[0]
        for home in h :
            if home - last_install >= mid :
                count += 1 
                last_install = home
        if count >= target :
            best = mid
            left = mid + 1 
        else :
            right = mid - 1
    return best

N, C = map(int, sys.stdin.readline().split())
hh = [int(sys.stdin.readline()) for _ in range(N)]
h = sorted(hh)
left = 0
right = max(h)
result = gongugi(left, right, C)
print(result)

최종 코드의 디버깅으로 이해하는 이진 탐색은 다음과 같다. 우선 디버깅 코드를 입력한 곳은 다음과 같다.

def gongugi(left, right, target):
    best = 0
    while left <= right :
					(생략)
        for home in h :
            if home - last_install >= mid :
                print(f"{home} - {last_install} - {mid} - {count}")
					(생략)
        if count >= target :
					(생략)
            print(best)
					(생략)

# 디버깅 코드 출력
home : 8 - last : 1 - mid : 4 - count : 1
home : 2 - last : 1 - mid : 1 - count : 1
home : 4 - last : 2 - mid : 1 - count : 2
home : 8 - last : 4 - mid : 1 - count : 3
home : 9 - last : 8 - mid : 1 - count : 4
best : 1
home : 4 - last : 1 - mid : 2 - count : 1
home : 8 - last : 4 - mid : 2 - count : 2
best : 2
home : 4 - last : 1 - mid : 3 - count : 1
home : 8 - last : 4 - mid : 3 - count : 2
best : 3
3 # 정답

mid는 처음 함수에서 설정한 ( left + right ) // 2 인 4 지점에서 시작한다.

mid = 4 : 설치 가능한 공유기 수가 부족하기에 설치에 실패한다. (count 1에서 멈춤)

mid = 1 : 가능하지만 더 큰 mid가 있을 수 있으니 계속 탐색한다

mid = 2 : 설치 3개 → OK → best 갱신, left 증가해서 더 큰 거리 도전

mid = 3 : 조건 만족하니까 best = 3

여기서 mid 2, 3은 count ≥ target 코드에서 3을 만족하기 때문에 best에 추가된다. 3까지 코드 출력을 원한다면 디버깅 코드의 위치를 이동하면 된다.

 

손 코딩으로 로직에 대한 기록

내가 짠 코드도 시간이 지난 후에 어떤 생각으로 짰었고 어떻게 동작하는지 기억이 안나는게 나의 문제점이다. 아래는 개인 기록용으로 스킵해도 무관하다. 

 

시행착오 1. mid가 아닌 distance를 직접 구하려 했다

처음엔 공유기 사이의 실제 거리인 distance를 직접 계산해서 그걸 정답으로 삼아야 한다고 생각했다. 하지만 이 문제에서 우리가 찾고자 하는 값은 공유기 사이 최소 거리의 최댓값이다. 이때 핵심이 되는 건 distance 자체가 아니라, 이 최소 거리의 후보값, 즉 mid를 어떻게 다루느냐다.

mid는 공유기 사이의 최소 거리를 나타내는 후보값으로, 이 값이 설치 가능한지 아닌지를 판단하기 위한 기준선이 된다.

또한 실제로 공유기를 설치할 때는 리스트 h에 담긴 집들의 좌표를 for home in h로 순회하면서, 이전에 설치한 위치인 last_installed와의 거리를 비교한다. 이 거리(home - last_installed)가 현재 후보값인 mid 이상일 때만 공유기를 설치하도록 한다.

즉, 우리가 구하려는 건 공유기를 설치할 수 있는 최소 거리(mid)의 최대값이기 때문에, 거리 distance를 매번 직접 구하거나 저장할 필요는 없다. 최종적으로 출력해야 하는 값은 설치에 성공한 가장 큰 mid 값이다.

시행착오 2. count, last_installed를 while 루프 밖에서 초기화했다

이진 탐색에서 매번 다른 거리(mid)를 기준으로 설치 가능 여부를 판단해야 하는데, 이전 상태의 count 나 설치 기준(last_installed)을 유지하면 잘못된 판단을 하게 된다. 설치 개수(count)와 마지막 설치 위치(last_installed)는 while문 안에서 매번 새로 초기화해줘야 정확한 설치 시뮬레이션이 가능하다.