문제 링크

https://www.acmicpc.net/problem/15686

문제 설명

• 집과 치킨집의 위치가 주어진다
• 치킨 거리란 집별 가장 가까운 치킨집 까지의 거리의 합이다
• 치킨집 중 m개를 선택할 때 치킨 거리의 최솟값 출력

풀이

• 모든 경우의 수 체크 (combinations)
• 그때 그때 거리 계산

후기

• 비교적 쉬웠다
• 집과 치킨집의 거리를 모두 계산해놓고 sort 해놓으면 더 빠를 것 같은데
• n, m이 크지 않아서 괜찮을 것 같았다

코드

def get_dist(combi):
    sum_dist = 0
    for hy, hx in houses:
        min_dist = float('inf')
        for sy, sx in stores:
            if (sy, sx) in combi:
                min_dist = min(min_dist, abs(hy-sy) + abs(hx-sx))
        sum_dist += min_dist
    return sum_dist


# init
from itertools import combinations
import sys
read = sys.stdin.readline
n, m = map(int, read().split())
board = [list(map(int, read().split())) for _ in range(n)]
houses, stores = [], []
for i in range(len(board)):
    for j in range(len(board[i])):
        if board[i][j] == 1:
            houses.append((i, j))
        elif board[i][j] == 2:
            stores.append((i, j))

# start
min_dist = float('inf')
for combi in combinations(stores, m):
    min_dist = min(min_dist, get_dist(set(combi)))
print(min_dist)