파이썬(Python)으로 두 도시에 사람 수를 균등하게 나눠 보낼 때 최소 비용 구하는 프로그램

costs라는 이름의 리스트가 하나 있다고 가정해 보겠습니다. 여기서 costs[i]는 [c1, c2] 형태로 표현되며, 이는 i번째 사람이 0번 도시로 이동할 때 c1만큼, 1번 도시로 이동할 때 c2만큼의 비용이 든다는 의미입니다. 우리의 목표는 두 도시에 정확히 같은 수의 사람들을 배치하는 것이며, 이때 발생하는 최소 총비용을 구해야 합니다.

예를 들어, 입력이 costs = [[2, 6], [10, 3], [4, 9], [5, 8]]라고 해보겠습니다. 이 경우 출력은 17이 됩니다. 0번과 2번 사람은 0번 도시로, 1번과 3번 사람은 1번 도시로 이동하기 때문입니다. 즉, 0번 도시의 이동 비용은 2+4=6이고, 1번 도시의 이동 비용은 8+3=11이므로 전체 비용은 6+11=17이 됩니다.

문제 해결 접근 방법

이 문제를 해결하는 핵심 아이디어는 그리디(Greedy) 기법입니다. 일단 모든 사람을 0번 도시로 보낸다고 가정하고 총비용을 계산한 뒤, 각 사람을 1번 도시로 옮길 때 추가로 드는 비용 차이(y−x)를 구합니다. 그다음 차액이 가장 작은 절반의 사람들, 즉 1번 도시로 보내는 것이 상대적으로 유리한 사람들을 골라 해당 차액을 총비용에 더해주면 최소 비용을 얻을 수 있습니다.

구체적인 해결 단계는 다음과 같습니다 −

s := 0으로 초기화합니다.
a := 새로운 빈 리스트를 생성합니다.
costs의 각 쌍 (x, y)에 대해 다음을 수행합니다 −
- s := s + x
- 리스트 a의 끝에 (y - x) 값을 추가합니다.
리스트 a를 오름차순으로 정렬합니다.
i를 0부터 (a의 길이 / 2) - 1까지 반복하며 다음을 수행합니다 −
- s := s + a[i]
s를 반환합니다.

정렬된 차액 리스트에서 앞부분 절반이 바로 '1번 도시로 보내는 것이 유리한 사람들'에 해당하므로, 해당 값들을 누적하여 더해주는 방식입니다.

예제 코드

아래 구현 예시를 통해 더 자세히 이해해 보겠습니다 −

def solve(costs):
    s = 0
    a = []
    for x, y in costs:
        s += x
        a += (y - x,)
    a.sort()
    for i in range(len(a) // 2):
        s += a[i]
    return s

costs = [[2, 6],[10, 3],[4, 9],[5, 8]]
print(solve(costs))

입력

[[2, 6],[10, 3],[4, 9],[5, 8]]