🔦 문제 링크
✍️ 풀이
레스토랑이 원으로 되어있는 것이 포인트이다.
원이기 때문에 출발지점이 어디가 되었든 모든 지점을 지날수 있다.
따라서, 어느 위치에서 시작할 수 있게 weak지점을 한 바퀴 이후로도 확장시킨다.
weak.append(weak[i]) for i in range(length)
첫번째로 어느 위치에서 방문을 시작할 지 정한다. 선택할 수 있는 방문 위치는 모든 위치이지만 취약 지점에서 시작하는 것이 항상 최선일 것이다. 우리는 취약지점 중 하나를 선택한다.
두번째로는 친구들이 가질 수 있는 순열 중 하나를 선택한 후 친구 하나를 선택한다.
첫번째에서 선택한 시작 지점과 친구의 거리를 더하면 갈수 있는 최대거리를 구할 수 있다.
세번째는 취약 지점 어디까지 커버가 가능한지 확인한다.
두번째에서 구한 최대거리와 시작지점을 고려한 취약지점까지 거리를 비교해서 취약지점이 더 멀다면 친구를 추가하고 그 친구의 거리만큼 최대거리를 증가시킨다. 만약, 최대거리가 더 멀다면 다음 취약지점도 커버가 가능한지 확인하게 된다. 이 때, 친구의 수는 정해진 수를 넘어서면 모든 취약 지점을 커버할 수 없는 것으로 판단한다.
🛠 코드
from itertools import permutations
def solution(n, weak, dist):
answer = 0
length = len(weak)
for i in range(length):
weak.append(weak[i] + n)
mn = len(dist) + 1
for start in range(length):
for per in list(permutations(dist, len(dist))):
count = 1
distance = weak[start] + per[count - 1]
for i in range(start, start + length):
if distance < weak[i]:
count += 1
if count > len(dist):
break
distance = weak[i] + per[count - 1]
mn = min(mn, count)
if mn > len(dist):
return -1
return mn📝 정리
원의 특성 - 어떤 지점에서 시작해도 모든 지점을 지날 수 있다.
🎈 참조
Go Go