문제 링크
풀이 과정
전체 코드
from itertools import permutations
def solution(n, weak, dist):
num_weak_points = len(weak) # 취약 지점 수
num_friends = len(dist) # 투입할 수 있는 친구 수
answer = 1e+9
# 취약 지점 확장 -> 시계 방향만 고려하기 위함
for idx in range(num_weak_points):
weak.append(weak[idx] + n)
# 각 출발 지점 별, 친구 배치 순서에 따른 친구 수 최소값 계산
for start_idx in range(num_weak_points):
for dists in permutations(dist, num_friends):
friends = 1 # 투입할 친구 수
destination = weak[start_idx] + dists[friends-1] # 도착 지점
for j in range(start_idx, start_idx+num_weak_points):
# 취약 지점이 친구 도착 지점보다 뒤에 있는 경우
if destination < weak[j]:
# 친구를 한 명 추가로 투입해야 함
friends += 1
# 백트래킹 -> 투입해야 할 친구가, 투입 가능한 친구 수보다 큰 경우
if friends > num_friends:
break
# 도착지 갱신
destination = weak[j] + dists[friends-1]
answer = min(answer, friends)
return answer if answer <= num_friends else -1
Python
복사