[백준/Python] 15686번 치킨 배달

삼성 SW 역량 테스트 기출 문제

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

---

---

Solution

	from itertools import combinations
	n, m = map(int, input().split(' '))
	maps = [list(map(int, input().split(' '))) for _ in range(n)]
	home, chicken = [], []
	for i in range(n):
	for j in range(n):
	if maps[i][j] == 1:
	home.append((i,j))
	elif maps[i][j] == 2:
	chicken.append((i,j))
	ans = 10000
	for i in combinations(chicken, m):
	tmp = 0
	for j in home:
	minVal = 10000
	for k in i:
	distance = abs(k[0] - j[0]) + abs(k[1] - j[1])
	minVal = min(minVal, distance)
	tmp += minVal
	ans = min(ans, tmp)
	print(ans)

view raw 치킨배달.py hosted with ❤ by GitHub

 

문제 유형 : 브루트 포스

 

난 누가 뭐래도 치킨보단 피자를 선호하지만

제목이 뭔가 귀여워서 풀어봤다.

 

도시에 있는 치킨집 중에서 M개 씩 조합(itertools의 combinations을 이용했다.)

그리고 고른 치킨집 경우와 각 집과의 거리를 구해서 치킨 거리가 가장 작은 치킨집 조합을 출력한다.

 

성공 ^_^