집이라는 배열이 있고 다른 값 k가 있다고 가정합니다. 여기서 house[i]는 거리를 따라 i번째 집의 위치를 나타냅니다. 거리에 k개의 우편함을 할당하고 각 집과 가장 가까운 우편함 사이의 최소 총 거리를 찾아야 합니다.
따라서 입력이 집 =[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.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
리스트 하우스 정렬
-
util() 함수를 정의합니다. idx, n, k
가 필요합니다. -
k가 1과 같으면
-
코어 :=주택[(n + idx)/2의 몫]
-
[|houses[i]의 모든 요소의 합계 반환 - core| 범위 idx에서 n까지의 각 i에 대해])
-
-
결과 :=무한대
-
idx ~ n 범위의 i에 대해 수행
-
n - i
-
루프에서 나오다
-
-
결과 :=결과의 최소값 및 util(idx, i, 1) + util(i+1, n, k - 1)
-
-
반환 결과
-
기본 방법에서 다음을 수행합니다.
-
return util(0, 집 크기 - 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