치킨 배달
백준 15686: https://www.acmicpc.net/problem/15686
Edge case
1. 문제조건
- 글 읽는데에 시간투자 많이 할 것
Code
1. itertools 사용
# 치킨 배달
# 15686
# 22/07/26/16:51
from itertools import combinations
n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
h = list()
ch = list()
for r in range(n):
for c in range(n):
if g[r][c] == 1:
h.append([r, c]) # House의 좌표 저장
elif g[r][c] == 2:
ch.append([r, c]) # Chicken House의 좌표 저장
nch = len(ch) # 치킨집의 개수
distance = [0] * nch
# 가게 수만큼 행렬을 만들어
# r1, c1 집 좌표
answer = int(1e9)
for cch in combinations(ch, m): # m가지 좌표 추출
tmp = 0
for r1, c1 in h:
min_d = int(1e9)
for r2, c2 in cch:
min_d = min(min_d, abs(r2-r1)+abs(c2-c1))
tmp += min_d
answer = min(answer, tmp)
print(answer)
2. Combination 구현
재귀를 이용한 방법
def combination(arr, n):
result = []
if n == 0:
return [[]]
for i in range(0, len(arr)): # 1번 루프라 하고
elem = arr[i]
rest_arr = arr[i+1 : ]
for c in combination(rest_arr, n-1): # 2번 루프라 하면
result.append([elem]+c)
return result
arr = [0, 1, 2, 3] 이고, n = 2 일 때
combination([0, 1, 2, 3], 2)
1번 루프
[0]+combination([1, 2, 3], 1)
1번 루프
- [0] + ([1] + combination([2, 3], 0))
- [0] + ([2] + combination([3], 0))
- [0] + ([3] + combination([], 0))
[1]+combination([2, 3], 1)
- [1] + ([2] + combination([3], 0))
- [1] + ([3] + combination([], 0))
[2]+combination([3], 1)
- [2] + ([3] + combination([], 0))
반응형
'코딩테스트' 카테고리의 다른 글
외벽점검 Python 정리 및 구현 (카카오 기출) (0) | 2022.07.28 |
---|---|
연구소 Python 정리 및 구현 (백준 14502, 삼성 SW 역량테스트 기출) (0) | 2022.07.28 |
기둥과 보 설치(2020 Kakao) 정리 및 코드 (0) | 2022.07.26 |
뱀(백준 3190) 정리 및 코드 (0) | 2022.07.25 |
[22.07.25] Tistory에 Github Markdown 특성 적용하기 (1) | 2022.07.25 |
댓글