외벽 점검 (lv3) & 피로도 (lv2)

문제 설명

레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다.

레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있습니다. 따라서 내부 공사 도중에도 외벽의 취약 지점들이 손상되지 않았는 지, 주기적으로 친구들을 보내서 점검을 하기로 했습니다. 다만, 빠른 공사 진행을 위해 점검 시간을 1시간으로 제한했습니다. 친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에, 최소한의 친구들을 투입해 취약 지점을 점검하고 나머지 친구들은 내부 공사를 돕도록 하려고 합니다. 편의 상 레스토랑의 정북 방향 지점을 0으로 나타내며, 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리로 나타냅니다. 또, 친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동합니다.

외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 return 하도록 solution 함수를 완성해주세요.

제한사항

• n은 1 이상 200 이하인 자연수입니다.
• weak의 길이는 1 이상 15 이하입니다.
  • 서로 다른 두 취약점의 위치가 같은 경우는 주어지지 않습니다.
  • 취약 지점의 위치는 오름차순으로 정렬되어 주어집니다.
  • weak의 원소는 0 이상 n - 1 이하인 정수입니다.
• dist의 길이는 1 이상 8 이하입니다.
  • dist의 원소는 1 이상 100 이하인 자연수입니다.
• 친구들을 모두 투입해도 취약 지점을 전부 점검할 수 없는 경우에는 -1을 return 해주세요.

---

 우선 가장 먼저 눈에 띄는 것은, weak이 원형 리스트라고 주어진 것이다. 또한 친구는 점검을 할 때 시계방향 또는 반시계방향으로 진행할 수 있으며, 최대 8명까지 동원 가능하다. weak의 시작지점 조합에 대해 dist 순열을 매칭시켜 각 친구가 각기 다른 점검 시작 지점에 놓이는 모든 경우에 대해 연산을 해도 1천만번이 안된다는 계산에 착안하여 완전탐색으로 접근해도 괜찮겠다는 생각을 했다. 친구들이 시작지점에 놓이는 모든 경우를 구하는것 까진 좋으나 그 이후 출발 지점을 기준으로 시계 방향으로 움직이느냐, 반시계 방향으로 움직이느냐 따지는것이 발목을 잡았다. 사실 이 문제에서 진행 방향은 상관이 없는 부분인데, 예를 들자면 n이 12, weak이 [1,3,5,10] 로 주어진다면, 문제에서 관심있는 것은 커버 가능 여부 그 자체이기 때문에 1->10으로 커버하는 경우나 10->1로 커버하는 경우나 다르지 않기 때문이다. 어떤 구간에 대해서 누구든 간, 방향이 어떻든 간 커버만 되면 상관 없기 때문에, dist를 순열로 늘어놓고 각 친구가 구간을 커버 가능한지만 따져주면 되는 문제이다. "피로도" 문제와 같은 순열을 이용한 완전 탐색 문제지만, 원형 리스트에서 출발 지점을 순회하며 탐색한다는 점이 다르다. 마지막으로 정리하자면 가장 중요한 것은 균열이 생긴 부분을 점검할 수 있는가 없는가만 따지면 되기 때문에, 그리고 순회하고 있는 리스트가 원형 리스트 이기 때문에 점검하는 친구를 순열로 순서만 바꿔준다면 진행 방향은 전혀 상관 없어진다는 것, 그리고 주어진 자료의 크기가 작기 때문에 완전탐색으로 접근해도 문제없다는 것이다.

from itertools import permutations

def solution(n, weak, dist):
    answer = int(1e9)
    length = len(weak)
    weak += list(map(lambda x : x+n,weak))
    for start in range(length):
        for friends in permutations(dist,len(dist)):
            cnt = 1
            cap = weak[start] + friends[cnt-1]
            for idx in range(start, start + length):
                if weak[idx] > cap:
                    cnt += 1
                    if cnt > len(dist):
                        break
                    cap = weak[idx] + friends[cnt-1]
            answer = min(answer,cnt)
    if not answer <= len(dist):
        return -1
    return answer

 겸사겸사 "피로도" 문제도 해결했는데, 코드 구조가 매우 유사해서 첨부한다.

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    for routes in permutations(dungeons,len(dungeons)):
        cnt = 0
        hp = k
        for req,cost in routes:
            if hp < req:
                break
            hp -= cost
            cnt += 1
        answer = max(answer,cnt)
    return answer