[2020 카카오 기출] 외벽 점검

 

programmers.co.kr/learn/courses/30/lessons/60062

---

문제 해설(tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/)을 보고 해결했습니다.

 

가장 중요한 건 원형으로 되어 있는 곳을 어떻게 탐색할 지 방법을 찾는 거 같습니다.

해설에 나와 있는 대로 인덱스를 하나씩 밀면서 뒤로 있는 인덱스값에는 + N만큼 더해줘서

아래처럼 원형으로 되어 있는 효과를 만드는 게 중요합니다.

N = 12 [1, 5, 6, 10] [5, 6, 10, 13] [6, 10, 13, 17] [10, 13, 17, 18]

 

그리고 나서는 dist의 크기 제한을 보면 8로 크기가 작습니다.

그래서 비트 바스킹을 통해 (예시 5명) 00000 ~ 11111 경우의 수를 생성해주고,

각 경우의 수 안에서도 거리가 다른 애들의 순서를 바꿔서 탐색할 수 있도록 순열을 생성해주면 됩니다.

 

1. 원형처럼 구현한 2차원 벡터를

2. 비트 마스킹 + 순열 조합으로 전부 탐색해보면 됩니다.

 

모두 N제한이 작기 때문에 시도해볼 수 있는 방법입니다.

---

코드: github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG60062.cc