문제 링크

풀이 과정

전체 코드

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