문제

링크

풀이

도시에 있는 치킨집 중 최대 M개를 고른 후 도시의 치킨 거리의 최솟값을 구하는 문제이다. 문제를 보고 조합이 가장 먼저 떠올랐다. 도시의 총 치킨집 수 C M (nCr 형태)을 구한 후 도시의 치킨 거리를 계산하여 최솟값과 비교 후 갱신하여 푸는 방법을 생각했다.

1. 도시의 총 치킨집 수 C M (nCr 형태)의 조합을 구한다.

2. 각 조합 경우마다 집의 최단 치킨 거리를 구한다.

3. 이후 도시의 치킨 거리를 구한다. (이 도시의 치킨 거리는 각 조합 경우마다 계산되는 도시의 치킨 거리!)

4. 각 조합의 경우의 도시의 치킨 거리와 최솟값을 비교한 후 갱신을 반복하여 최종 답을 구한다.

코드

import sys
from itertools import combinations

input = sys.stdin.readline
N, M = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(N)]

chicken = [(x, y) for x in range(N) for y in range(N) if city[x][y] == 2]
house = [(x, y) for x in range(N) for y in range(N) if city[x][y] == 1]
minimum = 1e9

for case in combinations(chicken, M):
    total = 0
    for i in range(len(house)):
        mid_sum = 1e9
        for c in case:
            mid_sum = min(mid_sum, abs(house[i][0] - c[0]) + abs(house[i][1] - c[1]))
        total += mid_sum
    if total < minimum:
        minimum = total

print(minimum)

더 빠르고 간결한 코드

import sys
from itertools import combinations

input = sys.stdin.readline
N, M = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(N)]

chickens = [(x, y) for x in range(N) for y in range(N) if city[x][y] == 2]
houses = [(x, y) for x in range(N) for y in range(N) if city[x][y] == 1]
minimum = 1e9

for case in combinations(chickens, M):
    total = 0
    for h in houses:
        total += min([abs(h[0] - c[0]) + abs(h[1] - c[1]) for c in case])
        # 이전에 계산한 도시의 치킨거리 최솟값보다 중간 계산중인 도시의 치킨거리값이 크거나 같으면 탐색 종료(시간복잡도 줄이는 조건)
        if minimum <= total: break
    if total < minimum:
        minimum = total

print(minimum)