카카오 2020 블라인드, 외벽점검

풀이

from itertools import permutations

def solution(n, weak, dist):
	#zip 함수로 구간간의 거리를 구한다.
	#[1, 5, 6, 10]
	#[5, 6, 10, 1]
	#[(1, 5), (5, 6) ...]
	#[4, 1 ...]
    distances = [b-a for a, b in zip(weak, weak[1:]+weak[:1])]
    
    # 마지막 구간의거리에는 n을 더해줘야한다.
    # 0이되면서 다시 1부터 증가하기 때문이다.
    #n-a + b
    distances[-1] += n
    answer = len(dist)+1
    
    # 어느 지점부터 순서대로 돌릴것인가
    for start in range(len(weak)):
        shifted = distances[start:] + distances[:start]
        
        # 친구들은 어떤순서로 투입시킬것인가
        for cases in permutations(dist):
            # 사용한 친구들의 갯수
            count = 0

            # 현재까지 온 위치
            pos = 0
            
            for friend in cases:
                # 현재 친구로 간 거리
                acc = 0
                count += 1
                
                # 현재 친구가 갈수 있는 거리만큼 구간을 탐색한다.
                while pos!=len(shifted) and acc+shifted[pos]<=friend:
                    acc += shifted[pos]
                    pos += 1
                
                # 다음 친구를 탐색할때는 새로운 구간부터 시작한다.
                # pos에서 pos+1까지 가기에 부족한것인지, 이미 pos까지는 왔기 때문이다.
                pos += 1
                if pos >= len(shifted):
                    answer = min(answer, count)
                    break

    # 만약 모든경우에서 다돌수 없다면 -1을 반환한다.
    return answer if answer!=len(dist)+1 else -1