[BOJ] 1062 가르침 - python

15686번: 치킨 배달

15686번: 치킨 배달

풀이

치킨집 M개만큼만 남겨가면서 치킨거리가 얼마인지 각각 계산해야하는데 결론은 다 해봐야 한다. combination사용해서 모든 경우를 다 하며 최소인 경우를 찾는다.

import sys
from itertools import combinations

def input():
    return sys.stdin.readline().rstrip()

N,M = map(int,input().split(" "))
maps = [list(map(int,input().split(" "))) for _ in range(N)]
house = [(a+1,b+1) for a in range(N) for b in range(N) if maps[a][b] == 1]
chicken = [(a+1,b+1) for a in range(N) for b in range(N) if maps[a][b] == 2]

#치킨거리 계산
def calculate(house,chicken):
    return abs(house[0] - chicken[0]) + abs(house[1] - chicken[1])

#모든 경우의 수 다 해서 치킨거리의 합이 가장 작은걸 채택
sum_min = float('inf')
for cand in combinations(chicken,M): #치킨집 후보들을 골라서 치킨거리 최소 구하기
    sum = 0
    for h in house: #각 집에서 치킨집까지의 치킨거리 구하기
        sum += min(calculate(h,c) for c in cand)
    sum_min = min(sum,sum_min) #후보 중 치킨거리 최솟값
print(sum_min)

얻어가는 것

• combinations for문에 바로 쓰기

for cand in combinations(chicken,M):
		pass

• 무한대

positive = float('inf')
negative = float('-inf')

• for문 + min사용하기

sum += min(calculate(1,cand) for cand in candidate)
#candidate에서 for문 돌린것들 calculate함수 결과 값 중 최소 값이 리턴됨

느낀점

"211115"

소요 시간 : 30min

• 생각보다 간단한 문제였는데 왜 골드인지 모르겠다
• 근데 for문 반복사용이 계속 헷갈린다. 조건 거는게 아직 익숙하지않다. 더 열심히 문제 풀자