출처 : https://www.acmicpc.net/problem/15686
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는
www.acmicpc.net
# Code
from itertools import combinations
## 맵크기(N), 치킨집 최대 선택가능개수(M)
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
## 빈칸(0), 집(1), 치킨집(2)
house = []
chicken = []
for i in range(N):
for j in range(N):
if board[i][j] == 1: house.append((i, j))
elif board[i][j] == 2: chicken.append((i, j))
minv = float('inf')
for ch in combinations(chicken, M):
sumv = 0
for home in house:
sumv += min([abs(home[0]-i[0])+abs(home[1]-i[1]) for i in ch])
if minv <= sumv: break
if sumv < minv: minv = sumv
print(minv)
|
cs |
In [33]:
from itertools import combinations
In [34]:
## 입력값 받기
## 맵크기(N), 치킨집 최대 선택가능개수(M)
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
잘 입력받았는지 확인
In [36]:
print(N, M)
for i in range(N):
print(board[i])
집과 치킨집에 대한 위치 정보를 저장하자.
In [37]:
## 빈칸(0), 집(1), 치킨집(2)
house = []
chicken = []
for i in range(N):
for j in range(N):
if board[i][j] == 1: house.append((i, j))
elif board[i][j] == 2: chicken.append((i, j))
In [38]:
house # 집 위치
Out[38]:
In [39]:
chicken # 치킨 집 위치
Out[39]:
최대 M개의 치킨집을 고를 수 있다고 문제에 명시되어 있다.
선택된 치킨집이 많으면 많을수록 거리가 최소가 될 가능성이 크다.
즉, 전체 치킨집 중에서 M개를 선택하되, 그 중에서 거리가 가장 최소가 되는 곳으로 골라야 한다.
In [40]:
minv = float('inf')
In [41]:
for ch in combinations(chicken, M):
sumv = 0
for home in house:
sumv += min([abs(home[0]-i[0])+abs(home[1]-i[1]) for i in ch])
if minv <= sumv: break
if sumv < minv: minv = sumv
In [42]:
print(minv)
'알고리즘 > [Python] 백준' 카테고리의 다른 글
(Python) 백준 5373번: 큐빙 (0) | 2020.03.11 |
---|---|
(Python) 백준 17144번: 미세먼지 안녕! (0) | 2020.03.10 |
(Python) 백준 14500번: 테트로미노 (0) | 2020.03.09 |
(Python) 백준 13458번: 시험 감독 (0) | 2020.03.06 |
(Python) 백준 12100번: 2048 (Easy) (0) | 2020.03.04 |