문제

"링크"

해결 방법

콤비네이션 함수가 있는지 이문제를 통해 처음 알았다.
위 함수를 모르고 풀려다보니 치킨집을 조합할 때 계속 막혔지만 이 함수를 알고 문제를 푸니 정말 간단하게 풀렸다.

1개 부터 M개까지의 치킨집 조합들이 있을 것이다.
각 조합마다 도시의 최소 치킨거리를 구한다.
구하는 방법은 집마다 치킨거리를 합해준다.
-> 정리만 잘 해내면 되게 단순하다

정답 코드

from itertools import combinations
import sys

def get_distance(y1, x1, y2, x2):
  result = abs(y1-y2) + abs(x1-x2)
  return result

input = sys.stdin.readline
N,M = map(int, input().split())

board = []
for _ in range(N):
  board.append(list(map(int, input().split())))

#집들 좌표 추출하기 and 치킨집 좌표 추출하기
house_places = []
chicken_places = []
for i in range(N):
  for j in range(N):
    if board[i][j] == 1:
      house_places.append((i,j))
    elif board[i][j] == 2:
      chicken_places.append((i,j))

result = 2100000000
for i in range(1,M+1):
  for chickens in combinations(chicken_places, i):
    #각 집마다 가장 적은 치킨거리 tmp에 더해주기
    tmp_result = 0
    for house in house_places:
      dis = 2100000000
      for chicken in chickens:
        tmp_dis  = get_distance(house[0], house[1], chicken[0], chicken[1])
        if tmp_dis < dis:
          dis = tmp_dis
      tmp_result += dis
    if tmp_result < result:
      result = tmp_result

print(result)

걸린 시간