외벽 점검

이 문제는 2020 카카오 신입 공채에서 나온 문제이다.
N은 전체 외벽의 개수, weak는 문제가 있는 외벽의 좌표, dist는 각 친구들이 이동할 수 있는 거리를 나타낸다. 제한 조건을 보았을 때, weak과 dist 리스트의 길이가 매우 짧은 것을 볼 수 있다.

이 문제는 weak에 있는 문제가 있는 외벽 좌표를 dist에 있는 친구들의 이동할 수 있는 거리를 이용해서 최소한의 인원을 사용해서 고쳐야한다. 여기서 고친다는 것은 dist의 요소에 있는 길이를 통해서 weak에 있는 좌표를 모두 커버한다는 것을 의미한다.

경우의 수를 생각해보자.
친구들의 투입 순서는 매우 중요하다. 어떤 친구가 먼저 외벽을 점검하러 가는지가 인원수 최솟값을 사용하는데 키포인트이다. 즉 순서를 생각하면서 모든 경우의 수에 대해서 점검을 해야한다. 순서를 고려하며 모든 경우의 수를 나타내는 것은 Permutations이다.

즉 현재 문제가 있는 외벽 좌표 위치에서 한 친구가 이동할 수 있는 거리를 더해서 다음 문제가 있는 외벽 좌표 위치보다 작은지 체크를 해야한다. 그래서 아래와 같은 코드를 설계했다.

from itertools import permutations

def solution(n, weak, dist):
    distLength = len(dist)
    weakLength = len(weak)
    for i in range(weakLength):
        weak.append(weak[i] + n)
        
    permu = list(permutations(dist, distLength))  # 순서를 고려한 모든 경우의 수
    answer = distLength + 1  # 친구의 최대 수를 넘을 수 없게 설정
    for start in range(weakLength):  # 맨 처음 위치부터 탐색 시작
        for friend in permu:  # permutations로 나온 모든 친구 투입 순서
            count = 1  # 투입한 친구 수
            position = weak[start] + friend[count - 1]  # 첫 친구가 커버할 수 있는 범위 설정
            for i in range(start, start + weakLength):  # 시작 위치부터 끝 지점까지 탐색
                if position < weak[i]:  # 친구가 커버할 수 있는 범위보다 약한 지점이 더 큰 경우
                    count += 1  # 새로운 친구 투입
                    if count > distLength:  # 모든 친구가 이미 투입된 경우에는 탈출
                        break
                    position = weak[i] + friend[count - 1]  # 다음 친구가 커버할 수 있는 범위 설정
            answer = min(answer, count)  # 최소값 체크
            
    if answer > distLength:  # 친구들로 점검하지 못한다면 -1 리턴
        return -1
    return answer
    
print(solution(12, [1, 5, 6, 10], [1, 2, 3, 4]))
print(solution(12, [1, 3, 4, 9, 10], [3, 5, 7]))