15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
https://www.acmicpc.net/problem/15686
문제
문제 해결을 위한 과정
이 문제의 경우 가장 중요했던 것은 조합 즉 combination을 이용하는 것이었습니다. 만일 a, b, c, d, e라는 5개의 치킨집이 있을 때 3개를 뽑는 경우라면 a, b, c와 a,c,b와 b,a,c와 b,c,a 등등 이렇게 뽑은 것이라면 같은 경우입니다. 즉 순서가 중요하지 않은 조합을 이용하여 해결하는 것입니다. 파이썬에서 조합을 사용하기 위해서는 다음의 코드를 추가합니다.
from itertools import combinations
이 방법을 통해 치킨집들중 입력받은 M개를 고른 후 각각의 집마다 치킨 거리를 구한 후 도시의 최소 치킨 거리를 구하면 됩니다.
문제 해결을 위한 팁
None
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
from itertools import combinations
def compute(data):
answer = 0
for i in range(len(house)):
a, b = house[i]
temp = int(1e9)
for x, y in data:
temp = min(temp, abs(x - a) + abs(y - b))
answer += temp
return answer
N, M = map(int, input().split())
town = []
house = []
store = []
for i in range(N):
town.append(list(map(int, input().split())))
for j in range(N):
if town[i][j] == 1:
house.append((i, j))
elif town[i][j] == 2:
store.append((i, j))
ans = int(1e9)
for data in combinations(store, M):
ans = min(ans, compute(data))
print(ans)
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 14502: 연구소(Python) (0) | 2020.12.05 |
|---|---|
| 백준 알고리즘 18352: 특정 거리의 도시 찾기(Python) (0) | 2020.12.04 |
| 백준 알고리즘 3190: 뱀(Python, c++) (0) | 2020.11.29 |
| 백준 알고리즘 1914: 하노이 탑 (0) | 2020.11.28 |
| 백준 알고리즘 18406: 럭키 스트레이트 (Python) (0) | 2020.11.27 |