문제 유형: 구현
collection에 combination을 쓰면 된다.
여담이지만 pypy로 채점 돌렸을때 메모리+런타임으로 1등 먹어서 살짝 기분이 좋았다 ㅎㅎ
시간이 지나면 한순간의 꿈일 것 같지만...
문제 포인트는 다음과 같다
1) 입력을 받으면서 집, 치킨집 위치를 튜플로 저장해서 배열에 넣어두기
2) 미리 각 집의 모든 치킨집 위치에 대한 걸 계산해서 배열에 저장해 두기(그렇다면 나중에 치킨집을 고르고 일일히 계산하지 않아도 된다)
3) 치킨집의 경우의 수를 combination으로 뽑고, 각 경우의 치킨 거리 계산하기
처음에 문제를 잘못 이해해서 현재 치킨집 수 = 남길 치킨집 수의 경우 일일히 비교하는 로직을 안 쓰고 바로 답을 구하는 모종의 방법을 사용했는데 그 로직에 문제가 있어서 틀렸다고 나왔다.
결국 알고리즘은 엣지케이스의 일반화가 가장 중요한 것 같다. 내가 짜 놓은 로직에 엣지케이스가 걸릴 수 있게 하는 거다.
코드는 다음과 같다.
import sys
from itertools import combinations
def sol(cmap, cpos, hops, survival) :
cnum = len(cpos)
h_arr = [[0 for _ in range(cnum)] for _ in range(len(hops))]
#h[i][j] : i번 집이 j번째 치킨집에 대한 치킨거리
for i in range(cnum):
col_val = cpos[i][0]
row_val = cpos[i][1]
for j in range(len(hops)):
dir = abs(col_val - hops[j][0]) + abs(row_val-hops[j][1])
h_arr[j][i] = dir
clist = list(range(cnum))
try_list = list(combinations(clist, survival))
minimum = sys.maxsize
for i in try_list:
#한 가지가 뽑히는 조합 구현
total = 0
for h in h_arr: #한 집에서 최소 치킨 거리를 계산하기
local_minimum = 5000
for j in i:
if h[j] < local_minimum:
local_minimum = h[j]
total = total + local_minimum
if minimum > total :
minimum = total
return minimum
N, M = map(int, input().split())
chicken_map = []
house_pos = []
chicken_pos = []
for i in range(N):
row = list(map(int, input().split()))
for j in range(N):
if row[j] == 2:
chicken_pos.append((i, j))
if row[j] == 1:
house_pos.append((i, j))
chicken_map.append(row)
print(sol(chicken_map, chicken_pos, house_pos, M))
'Algorithm' 카테고리의 다른 글
[C++] 문자열로 곱셈과 덧셈 구현하기 (1) | 2022.12.05 |
---|---|
[BOJ][Python3]2504.괄호의 값 (2) | 2022.11.27 |
[BOJ][Python3]14501.퇴사 (0) | 2022.10.26 |
[Leetcode][Python3] 135. Candy (0) | 2022.04.26 |
[Leetcode][Python3] 269. AlienDictionary (0) | 2022.04.25 |
댓글