[프로그래머스] 외벽 점검 - python

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/60062

프로그래머스

처음에는 그리디 방식으로 접근을 해보았는데 탐욕적 선택을 해야하는 상황을 정의하기가 쉽지 않아서 완전 탐색으로 풀이했습니다. weak의 최대 길이 15, dist 최대 길이 8인 것으로 보았을 때 완전 탐색으로 풀이가 가능합니다.

 

풀이 방식은 다음과 같습니다. 결국 목표는 '원형인 외벽의 취약점을 모두 방문하기' 이므로 취약점의 위치에 n을 더해서 weak 배열에 추가해주면 됩니다. ex) n = 12, [1, 5, 6, 10] -> [1, 5, 6, 10, 13, 17, 18, 22]

 

그 다음으로는 완전 탐색을 위해서 시작점을 지정하고 해당 시작점을 기준으로 친구들을 나열했을 때의 모든 경우의 수에 따른 취약점을 모두 방문할 수 있는지와 필요한 친구들의 수를 체크해주면 됩니다.

 

처음 시작점이 5라고 가정하고 dist의 순서가 [2, 3, 1, 4]라고 가정했을 때 처음 시작점인 5를 방문하기 위해 1명이 필요하고 처음 출발하는 친구가 2만큼 걸어갈 수 있으므로 7까지 이동하게 됩니다. 이때 자연스럽게 6 취약점을 방문하게 됩니다. 다음 취약점의 위치가 10이므로 친구가 한명 더 필요하게 되고 다음 친구는 3만큼 이동 가능하므로 13까지 이동하면서 최약점 13을 방문하게 됩니다. 취약점 4군데를 모두 방문했으므로 탐색을 종료하게 되어 현재의 경우에서는 2명의 친구만 있으면 모든 취약점을 방문할 수 있게 됩니다.

 

# 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/60062
from itertools import permutations

def solution(n, weak, dist):
    answer = 10
    w_len = len(weak)

    for i in range(w_len):
        weak.append(weak[i] + n)

    for i in range(w_len):
        # 친구들의 순열
        for d in list(permutations(dist, len(dist))):
            cnt = 1
            pos = weak[i] + d[cnt - 1]

            # len(weak)의 수 만큼 방문
            for j in range(i, i + w_len):
                # 현재의 취약점은 방문할 수 없는 경우
                if pos < weak[j]:
                    cnt += 1
                    # 모든 친구들을 사용했을 때
                    if cnt > len(dist):
                        break

                    # 다음 친구가 방문할 수 있는 위치 갱신
                    pos = weak[j] + d[cnt - 1]
            answer = min(answer, cnt)

    if answer > len(dist):
        return -1

    return answer