1. 문제
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
2. 접근 방법
총 치킨 가게에서 M개만 골라야하니 -> 조합으로 풀면 되겠다고 생각했습니다.
조합을 배열에 담고, 해당 치킨 가게들 중 집과 가장 가까운 거리에 있는 치킨 거리를 총합에 더해주고,
결과 값인 minAns를 갱신해주면 된다고 생각했습니다.
그리고 NxN에서 N의 최대값이 50이고, M의 최대값이 13이라 각각의 조합에서 완탐을 해도 될거같은 느낌을 받았습니다.
흠 ~! 완탐이라는 표현이 맞는지 ^-^~!
여튼 조합을 itertools로 구현하지 않고 직접 구현해서 풀었슴다. (아마 라이브러리 사용이 안될 것이라고 생각하므로)
3. 코드
python
def solve(cnt, total):
global minAns, chicken_group, homes
if cnt == len(homes):
minAns = min(minAns, total)
return
temp_dist = 1e9
for i in range(M):
temp_dist = min(temp_dist, abs(homes[cnt][0]-chicken_group[i][0]) + abs(homes[cnt][1]-chicken_group[i][1]))
total += temp_dist
solve(cnt+1, total)
def comb(cnt, start):
global M
if cnt == M:
solve(0, 0)
return
for i in range(start, len(chickens)):
chicken_group.append(chickens[i])
comb(cnt+1, i+1)
chicken_group.pop()
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
homes = []
chickens = []
minAns = 1e9
for y in range(N):
for x in range(N):
if board[y][x] == 1:
homes.append((x, y))
elif board[y][x] == 2:
chickens.append((x, y))
chicken_group = []
comb(0, 0)
print(minAns)
4. 마치며
예전에는 조합 만드는 것두 쩔쩔매던 나였지만 ! 이제 조합도 직접 구현할 수 있다 이겁니다 !