본문 바로가기
알고리즘 문제/BOJ

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

by 햄과함께 2021. 1. 1.
320x100

문제 : 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

320x100

'알고리즘 문제 > BOJ' 카테고리의 다른 글

[BOJ][20528] 끝말잇기  (0) 2021.01.01
[BOJ][17143] 낚시왕  (0) 2020.11.15
[BOJ][17144] 미세먼지 안녕!  (0) 2020.11.08
[BOJ][16235] 나무 재테크  (0) 2020.11.07
[BOJ][14890] 경사로  (0) 2020.11.06

댓글