[백준 20529] 가장 가까운 세 사람의 심리적 거리 [Java]

백준 20529 - 문제

백준 20529 - 입/출력

---

풀이

N개의 중 3개의 MBTI에 대해서 가장 작은 심리적 거리를 구해야 한다.

모든 경우의 수를 전부 탐색하면 N^3 이기에 당연히 시간초과가 발생할 것이다.

때문에 구한 거리가 0인지 확인을 하고, 중간에 loop를 빠져나와야 한다.

비둘기집 원리를 통해 더 줄여보자.

MBTI에 대한 심리적 거리의 최선의 경우는 뭘까?

bruteforce이지만, 심리적 거리가 0인 경우 더 이상의 탐색이 무의미하기에 중단 해주어 시간초과가 발생하지 않는다.

 

심리적 거리가 0이라는 조건 이후의 탐색이 무의미하다면, 심리적 거리가 0이 되는 최악의 경우는 무엇일까?
바로 비둘기집 원리에 따른 33명이다. 

 

서로 다른 MBTI를 가진 16명이 2명씩 총 32명 있을 경우 심리적 거리는 0이 될 수 없다.

33명부터 동일한 MBTI를 가진 인원이 3명이 되기 때문에 비로소 심리적 거리가 0임을 보장할 수 있다.

때문에 입력으로 주어지는 MBTI의 구성이 어떻든, 33명 이하 일 때 심리적 거리가 0이 되어야 하므로 

입력과 탐색범위를 33명 이하로 제한하면 더 빠르게 풀 수 있을 것이다.

---

소스코드

소스코드 보기

---

출처

20529번: 가장 가까운 세 사람의 심리적 거리