[백준 15686] 치킨 배달

• 첫 풀이
  • 조합 적용을 못해서 도중에 멈춤

#집과 가장 가까운 치킨집 사이 거리
#도시 치킨 거리= 모든 집 치킨 거리 합
#가장수익을 많이 낼 수 있는 치킨집 개수 : M 
#최대 M개 구하고 나머지 폐업
#치킨 거리가 가장 작게
from collections import deque
from itertools import combinations as c

n,m= map(int,input().split())
home=deque()
chick=deque()
cnt=0
dir=[]

for r in range(1,n+1):
    c=list(map(int,input().split()))
    for idx, v in enumerate(c):
      if v==1:
        home.append((r,idx+1)) #집 위치
      elif v==2:
        cnt+=1
        chick.append((r,idx+1)) #치킨집 위치

for _ in range(cnt):
  r,c=chick.popleft()
  dir=[]
  for h in home:
    hr, hc=h #tuple 에서 각각 값받아올때 그냥 () 바로 넣으면됨
    dir.append(abs(hr-r)+ abs(hc-c))
  chick.append(dir)

#각 합
for r in chick:
  print(r)

#최대 m개의 치킨집을 선택
result=0
#row: 치킨집 개수
#col: 집 개수
for i in range(len(home)):
  dmin=101 #거리 최소 인덱스 구하기 위함
  for j in range(cnt): 
    dmin= min(dmin,chick[j][i])
  result+=dmin
print(result)

 

• 풀이 완료
  • 최대 M개 이기 때문에 조합으로 나온 행들 중에 그 이하로 선택되어도 괜찮음

#도시 치킨 거리= 모든 집 치킨 거리 합
#최대 M개 구하고 나머지 폐업
#치킨 거리가 가장 작게
from collections import deque
from itertools import combinations

n,m= map(int,input().split())
home=[]
chick=[]
cnt=0
dir=[]

for r in range(1,n+1):
    c=list(map(int,input().split()))
    for idx, v in enumerate(c):
      if v==1:
        home.append((r,idx+1)) #집 위치
      elif v==2:
        cnt+=1
        chick.append((r,idx+1)) #치킨집 위치

#치킨집 별, 집들과의 거리
for _ in range(cnt):
  r,c=chick.pop(0)
  dir=[]
  for h in home:
    hr, hc=h 
    dir.append(abs(hr-r)+ abs(hc-c))
  chick.append(dir)

check=[i for i in range(len(chick))]

clst=list(combinations(check, m))

answer=1e9
for i in range(len(clst)):
    result=0
    for j in range(len(home)):
        dmin=1e9
        for k in clst[i]:
            dmin=min(dmin, chick[k][j])
        result+=dmin
    answer=min(answer,result)

print(answer)