거리를 따라 위치한 집들을 나타내는 houses 배열과 우편함 개수 k가 주어졌다고 가정해 봅시다. 여기서 houses[i]는 거리 위에 있는 i번째 집의 좌표를 의미합니다. 우리는 이 거리에 k개의 우편함을 배치해야 하며, 각 집에서 가장 가까운 우편함까지의 거리 합이 최소가 되도록 만들어야 합니다.
문제 예시 이해하기
입력이 houses = [6, 7, 9, 16, 22], k = 2라고 해보겠습니다. 이때 정답은 9입니다. 7과 18 위치에 우편함을 설치하면 각 집에서 가장 가까운 우편함까지의 거리 합은 다음과 같습니다.
|6−7| + |7−7| + |9−7| + |16−18| + |22−18| = 1 + 0 + 2 + 2 + 4 = 9
핵심 아이디어
하나의 우편함으로 여러 집을 커버할 때는 해당 구간 집들의 중앙값(median) 위치에 우편함을 두는 것이 최적입니다. 절댓값 거리의 합은 중앙값에서 최소화되기 때문입니다. 따라서 이 문제는 "집들을 k개의 그룹으로 나누고, 각 그룹의 중앙값 위치에 우편함을 배치한다"는 관점으로 바꿔 생각할 수 있습니다.
풀이 접근 방법
재귀적으로 구간을 분할하면서 각 구간마다 하나의 우편함을 배치하는 방식으로 문제를 해결할 수 있습니다. 단계는 다음과 같습니다.
정렬: houses 리스트를 오름차순으로 정렬합니다.
util(idx, n, k) 함수 정의: idx부터 n까지의 집들에게 k개의 우편함을 배치할 때의 최소 거리를 계산합니다.
k가 1인 경우: core를 houses[(n + idx) // 2], 즉 현재 구간의 중앙값으로 설정하고, idx부터 n까지 모든 i에 대해 |houses[i] − core|의 합을 반환합니다.
k가 1보다 큰 경우: result를 무한대로 초기화한 뒤, i를 idx부터 n까지 반복하며 다음을 수행합니다.
- n − i < k − 1이면 남은 집의 수가 부족하므로 반복문을 종료합니다.
- result를 min(result, util(idx, i, 1) + util(i + 1, n, k − 1))로 갱신합니다.
계산된 result를 반환합니다.
메인 호출: 전체 집 범위에 대해 util(0, len(houses) − 1, k)의 값을 반환합니다.
구현 예제
아래 코드를 통해 실제 구현 과정을 확인해 보겠습니다.
def solve(houses, k):
houses.sort()
def util(idx, n, k):
if k == 1:
core = houses[(n + idx) // 2]
return sum([abs(houses[i] - core) for i in range(idx, n + 1)])
result = float('inf')
for i in range(idx, n + 1):
if n - i < k - 1:
break
result = min(result, util(idx, i, 1) + util(i + 1, n, k - 1))
return result
return util(0, len(houses) - 1, k)
houses = [6,7,9,16,22]
k = 2
print(solve(houses, k))입력
[6,7,9,16,22], 2
출력
9
마무리 및 성능 참고
이 풀이는 구간을 재귀적으로 분할하는 방식으로 동작하며, 로직이 직관적이고 이해하기 쉽다는 장점이 있습니다. 다만 집의 개수와 k가 커질수록 연산량이 급격히 늘어날 수 있습니다. 이를 개선하려면 util 함수의 결과를 딕셔너리 등에 저장해 두는 메모이제이션(memoization) 기법을 적용하면 중복 계산을 제거하여 실행 속도를 크게 향상시킬 수 있습니다.