[BOJ][20529] 가장 가까운 세 사람의 심리적 거리

문제 : www.acmicpc.net/problem/20529

---

완전탐색을 하면 O(N^3)의 시간복잡도를 가지는데 제한 사항을 보면 N이 10만이기 때문에 TLE가 발생할것이다.

시간을 줄일만한게 어디없나 보면 MBTI는 총 16가지이다. 이걸 사용할 수 있을 것 같다.

사람들은 16개 중 하나를 가지는데 최대한 겹치지 않게 MBTI를 가지고 있다고 가정하자. 

그럼 16명의 사람까지는 동일한 MBTI를 가지지 않고 모두 고유한 값을 가질 수 있다.

16 ~ 16*2 명의 사람까지는 동일한 MBTI를 가지는 사람이 최대 두 명까지 나올 수 있다.

그러면 16 * 2 + 1 이상의 사람은 어떻게 되는가. 16*2 명의 사람들은 동일한 MBTI를 가지는 사람이 2명이 있다. (각 MBTI 모두 2명의 사람)

따라서 한 명이 어떤 MBTI를 가지던지 어떠한 MBTI에 속하는 사람은 반드시 3명 이상이된다.

3명의 사람이 같은 MBTI를 가지면 심리적 거리는 0이 되므로 항상 정답은 0이된다.

즉, 16 * 2명 이하의 경우만 완전탐색으로 심리적 거리를 구하며 최소 값을 구하면 되고.

16*2 + 1 명 이상부터는 최소값이 0이된다.

 

시간복잡도는 O(N^2). N = 16 * 2.

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/BOJ/20529.%20%EA%B0%80%EC%9E%A5%20%EA%B0%80%EA%B9%8C%EC%9A%B4%20%EC%84%B8%20%EC%82%AC%EB%9E%8C%EC%9D%98%20%EC%8B%AC%EB%A6%AC%EC%A0%81%20%EA%B1%B0%EB%A6%AC.cpp