문제 링크

문제 해설

Idea

  • Combinations
  • 최대 집의 개수가 100, 최대 치킨집의 개수가 13으로 매우 적은 경우의 수를 가지고 있기 때문에,
    모든 조합에 대한 완전탐색을 통해 최소 거리를 계산
  • 초기에는 집에 대한 치킨 거리가 작은 치킨집을 우선적으로 선발해서,
    폐업하지 않은 치킨집에 대한 치킨 거리의 최소 합을 계산했지만 틀림
  • 이후 combinations 모듈을 활용한 완전탐색을 통해 통과

Time Complexity

  • O(N * nCr) ~ 100,000

Data Size

  • N: 2 <= int <= 50
  • M: 1 <= int <= 13
  • cell in (0, 1, 2)
  • count(house): 1 <= int < 2N
  • count(chicken): M <= int <= 13

해설 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

from itertools import combinations
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
city = {'0':list(),'1':list(),'2':list()}
for r in range(N):
    for c,i in enumerate(input().split()):
        city[i].append((r,c))
houses, chickens = city['1'], city['2']
diff = lambda c1,c2: abs(c1[0]-c2[0])+abs(c1[1]-c2[1])

# =============== 1안 (틀림) ===============

house_cost = {chicken:0 for chicken in chickens}
chicken_cost = {house:house_cost.copy() for house in houses}

for house in houses:
    for chicken in chickens:
        cost = diff(house,chicken)
        chicken_cost[house][chicken] = cost
        house_cost[chicken] += cost

city_cost = 0
open = [chicken for chicken,cost in sorted(house_cost.items(), key=lambda x: x[1])[:M]]
for house, costs in chicken_cost.items():
    city_cost += min([cost for chicken,cost in costs.items() if chicken in open])

# =============== 2안 (통과) ===============

city_cost = sys.maxsize
for comb in combinations(chickens, M):
    cost = 0
    for house in houses:
        cost += min([diff(house,chicken) for chicken in comb])
    city_cost = min(city_cost,cost)

print(city_cost)