dist 가 최대 길이가 8 로 매우 작기 때문에 8! 개의 모든 순열을 조합해 볼 수 있다.
점검을 왼쪽으로도, 오른쪽으로도 가능하기 때문에 1,2,3 이렇게 있으면 1,2,3,4, N+1, N+2, N+3 해서 생각해볼 수 있다. 2부터 반시계로 4까지 가는건 4 부터 n+2 까지 시계방향으로 가는것과 같다.
그래서 weak 배열은 2*N-1 의 길이가 된다.
그래서 1 부터 4까지, 4 부터 N+3 까지 모두 탐색해보면 답을 찾을 수 있다. dist 배열은 next_permutation 으로 순열을 뽑아내서 각 취약지점을 각각의 친구들이 탐색했을때 몇명이 탐색했는지, 모두 탐색했는지 확인해 보면 된다.
next_permutation 을 쓰기위해 dist 배열을 정렬해두고 각 단계마다 함수를 실행한다.
함수안에서는 시작값을 받는데 이 시작값은 1 부터 4 까지다. 4에서 시작하는 탐색은 시간 반대 방향을 의미한다. 현재 위치에서 dist[i] 값으로 탐색이 가능한 범위를 정하고 코드에선 int to = weak[weak_idx] + dist[dist_idx]; 에 해당한다.
전체를 탐색한 경우는 if (cnt == originWeakSize 조건으로 확인 가능하다. (모든 취약지점을 탐색한 경우)
이 조건이 있기 때문에 to >= weak[weak_idx] 구문에서 out of range 에러를 방지할 수 있다. start 값이 최대 N 만큼만 들어오기 때문에 만약 N 에서 시작해서 N 개만큼 탐색할 경우 저 조건문에 걸리기 때문이다.
60062. 외벽점검
문제링크
설계
dist가 최대 길이가 8 로 매우 작기 때문에8!개의 모든 순열을 조합해 볼 수 있다.점검을 왼쪽으로도, 오른쪽으로도 가능하기 때문에
1,2,3이렇게 있으면1,2,3,4, N+1, N+2, N+3해서 생각해볼 수 있다. 2부터 반시계로 4까지 가는건 4 부터 n+2 까지 시계방향으로 가는것과 같다.그래서
weak배열은2*N-1의 길이가 된다.그래서 1 부터 4까지, 4 부터 N+3 까지 모두 탐색해보면 답을 찾을 수 있다.
dist배열은next_permutation으로 순열을 뽑아내서 각 취약지점을 각각의 친구들이 탐색했을때 몇명이 탐색했는지, 모두 탐색했는지 확인해 보면 된다.next_permutation을 쓰기위해dist배열을 정렬해두고 각 단계마다 함수를 실행한다.함수안에서는 시작값을 받는데 이 시작값은 1 부터 4 까지다. 4에서 시작하는 탐색은 시간 반대 방향을 의미한다. 현재 위치에서
dist[i]값으로 탐색이 가능한 범위를 정하고 코드에선int to = weak[weak_idx] + dist[dist_idx];에 해당한다.전체를 탐색한 경우는
if (cnt == originWeakSize조건으로 확인 가능하다. (모든 취약지점을 탐색한 경우) 이 조건이 있기 때문에to >= weak[weak_idx]구문에서 out of range 에러를 방지할 수 있다. start 값이 최대N만큼만 들어오기 때문에 만약N에서 시작해서N개만큼 탐색할 경우 저 조건문에 걸리기 때문이다.시간복잡도
weak 길이: M, dist 길이: N 일때
`O(N!*M)