문제 설명
레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다.
레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 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 해주세요.
전체 코드
from itertools import permutations
def solution(n, weak, dist):
INF=987654321
answer = INF
perm=list(permutations(dist,len(dist)))
weak_set=set()
weak_list=[]#원형이므로 2배 길이로 만듬
for i in range(len(weak)):
weak_list.append(weak[i])
weak_set.add(weak[i])
for i in range(len(weak)):
weak_list.append(weak[i]+n)
#weak의 시작점을 나타내는 인덱스
start_index=0
while start_index<len(weak):
for p in perm: # (4,2,3,1)등의 순열
#weak_list의 현재 위치를 나타내는 인덱스.
weak_index=start_index
#커버한 곳을 담는 set
cover_set=set()
for i in range(len(p)):
num=p[i]
#weak_list[weak_index]부터 weak_list[weak_index]+num까지 커버할 수 있다는 의미
covered=weak_list[weak_index]+num
#커버할 수 있는 weak_list의 원소들을 set에 담기. 그리고 다음 weak_index도 계산해놓기
#예를 들어 weak_list=[1,5,6,10,13,17,18,22], p=[4,2,3,1], weak_index=0이라 하자.
#covered=weak_list[0]+4=5인데, 이는 weak_list에서 5보다 작거나 같은 수는 커버 가능하다는 뜻이다.
#따라서 p의 다음 순서 2를 놓을 위치는 weak_list의 6이어야 한다.
while weak_index<len(weak_list) and covered>=weak_list[weak_index]:
cover_set.add(weak_list[weak_index]%n)
weak_index+=1
if cover_set & weak_set==weak_set:
answer=min(answer,i+1)
break
start_index+=1
if answer==INF:
return -1
return answer해설
문제의 핵심을 올바르게 파악하자.
취약 지점 weak는 최대 15개이고 원형으로 배치되어 있다. 그리고 친구들이 갈 수 있는 거리 dist는 최대 8이다. 충분히 작은 수이다.
처음에는 weak에 대해 조합, dist에 대해 순열을 해서 각각 매핑해서 풀었다. 하지만 이렇게 하면 효율성에서 통과할 수 없다.
이유는 다음과 같다. nCr의 시간 복잡도는 2^n인데, 최대 15이므로 2^15이므로 32,768개이고 nPr의 시간 복잡도는 n!이고 최대 8이므로 8! =40320이다.
매핑해야 하므로 32768 * 40320=1,321,205,760이나 된다. 10억이 넘어가는 수이므로 시간초과가 날 수 밖에 없는 풀이였다.
따라서 더 효율적인 풀이를 생각해야 했다.
문제의 핵심은 취약 지점에 순서대로 배치했을 때 전부 커버할 수 있는가이다.
위 그림(dist=[1,2,3,4])을 예로 들어보자.
(원형이긴 하지만 직선 형태로 변환할 수 있다.
예를 들어 weak=[1,5,6,10]을 직선으로 만들면 [1,5,6,10,13,17,18,22]로 바꿀 수 있다. 이렇게 바꾸면 시계 방향으로만 생각할 수 있어서 편리하다.)
중요한 것 중 하나는 '띄엄 띄엄 배치해서는 안된다'는 것이다.
예를 들어 1번 취약지점에 dist=2를 배치하고 6번 지점에 dist=1을 배치하는 것은 띄엄 띄엄 배치한 것이므로 모든 취약지점을 커버할 수가 없다.
올바르게 배치하는 방법 중 하나는 1번에 dist=2, 5번 지점에 dist=1 (5와 6 커버 가능), 10번지점에 dist=3을 순서대로 배치하는 것이다.
두 번째는 다음 취약지점에 배치하는 원리이다. 예를 들어 1번 지역에 dist=4를 배치한다고 해보자.
그러면 취약 지점 1번부터 5번까지는 dist=4가 커버할 수 있다. 그러면 다음 취약 지점은 어디일까?
띄엄 띄엄 배치해서는 안되므로 취약 지점 6부터 시작해야 한다. 즉, 바로 이전 사람이 미처 커버 못했던 것중 가장 순서가 빠른 것을 다음 취약지점으로 지정해야 한다.
마지막으로 '시작 지점에 따라 배치해야 하는 인원수가 달라질 수 있다'는 것이다.
위 그림에서 weak=[1,3,4,9,10]이고 dist=[3,5,7]이다. dist에 대해 순열로 만든 것중 p=[7,5,3]이라고 하자.
시작지점 1번부터 배치하면, dist=7이 1,3,4를 커버한다. 그리고 dist=5가 9,10을 커버한다. 2명이 필요하다.
시작지점 3번부터 배치하면 dist=7이 3,4,9,10을 커버하고 dist=5가 1을 커버하므로 2명이 필요하다.
시작지점 4부터 배치하면 dist=7이 3,4,9,10을 커버하고 dist=5가 1을 커버하므로 2명이 필요하다.
시작지점 9부터 배치하면 dist=7이 9,10,1,3,4를 전부 커버할 수 있으므로 1명만 필요하다.
시작지점 10부터 배치하면 dist=7이 10,1,3,4를 커버하고 dist=5가 9를 커버하므로 2명이 필요하다.
이와 같이 같은 순열 p에 대해서도 시작지점에 따라 필요한 인원수가 다르다.
n(≤3)중 반복문에서 어느게 바깥 반복문인지 헷갈릴 때의 팁
(@@@일반적으로 n>3이면 반복문보단 재귀가 낫다.)
n≤3인 n중 반복문에서 무엇을 바깥 반복문으로 해야할 지 헷갈린다면 다음 그림을 떠올려보면 도움이 된다.
바깥 반복문의 요소가 기준이고, 안쪽 반복문의 요소들이 해당 기준에 맵핑되는 요소들이다.
이 문제에서도 이를 적용할 수 있다.
순열 p=[4,2], weak=[1,5]일 때 시작 지점 1부터 시작해서 순열 p의 요소들을 순서대로 배치한다.
그 다음에는 시작 지점을 5부터 해서 순열 p를 순서대로 배치한다.
즉 weak의 요소에 대해 순열 p의 요소들이 맵핑되므로 weak의 요소가 기준이다.
따라서 weak의 요소를 바깥 반복문으로 해야한다.
