[Python] 백준 15686번: 치킨 배달
https://www.acmicpc.net/problem/15686
풀이
m
개의 치킨 집을 선택할 때 치킨집과 일반집 사이의 치킨거리(일반집과 가장 가까운 치킨집과의 거리)의 합을 구해야 함.
- 먼저 치킨집 일반집의 좌표(i,j)를
puradak
과 house
리스트에 저장
- combinations를 이용해서 치킨집을
m
개 선택 했을 때의 조합을 구함
- 순회를 돌면서 일반집 하나와 치킨집 사이의 최단거리를 치킨거리에 추가
- 조합에서 구한 치킨 거리 중 가장 작은 치킨거리를 출력
코드
import sys
from itertools import combinations
input = sys.stdin.readline
n,m = map(int, input().split())
maps = [list(map(int,input().split())) for _ in range(n)]
# 치킨집과 일반집 위치 구하고, 각 위치에 대해서 치킨거리를 구해야함.
puradak = []
house = []
for i in range(n):
for j in range(n):
if maps[i][j] == 1:
house.append([i,j])
elif maps[i][j] == 2:
puradak.append([i,j])
# 치킨집을 m개 선택했을때 조합
combs = list(combinations(puradak, m))
cand = []
for comb in combs:
answer = 0
for h in house:
x1, y1 = h
dist = int(1e9)
for c in comb:
x2, y2 = c
dist = min(dist, abs(x1-x2) + abs(y1-y2))
answer+=dist
cand.append(answer)
print(min(cand))
Author And Source
이 문제에 관하여([Python] 백준 15686번: 치킨 배달), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@joniekwon/Python-백준-15686번-치킨-배달
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
m
개의 치킨 집을 선택할 때 치킨집과 일반집 사이의 치킨거리(일반집과 가장 가까운 치킨집과의 거리)의 합을 구해야 함.puradak
과 house
리스트에 저장m
개 선택 했을 때의 조합을 구함import sys
from itertools import combinations
input = sys.stdin.readline
n,m = map(int, input().split())
maps = [list(map(int,input().split())) for _ in range(n)]
# 치킨집과 일반집 위치 구하고, 각 위치에 대해서 치킨거리를 구해야함.
puradak = []
house = []
for i in range(n):
for j in range(n):
if maps[i][j] == 1:
house.append([i,j])
elif maps[i][j] == 2:
puradak.append([i,j])
# 치킨집을 m개 선택했을때 조합
combs = list(combinations(puradak, m))
cand = []
for comb in combs:
answer = 0
for h in house:
x1, y1 = h
dist = int(1e9)
for c in comb:
x2, y2 = c
dist = min(dist, abs(x1-x2) + abs(y1-y2))
answer+=dist
cand.append(answer)
print(min(cand))
Author And Source
이 문제에 관하여([Python] 백준 15686번: 치킨 배달), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@joniekwon/Python-백준-15686번-치킨-배달저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)