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

문제

예시

풀이

'비둘기집의 원리'를 사용하면 해결 가능하다.

비둘기집의 원리

[비둘기집 원리

비둘기집 원리란? 여러개의 데이터를 그룹 짓는 상황에서 경우의 수를 따질 때, 사용할 수 있는 알고리즘이다. 예시 1. 옷장에 흰색 양말 10개와 검은색 양말 10개가 있다고 할 때, 같은 색상의 양

sdsf1225.tistory.com](https://sdsf1225.tistory.com/75)

MBTI는 총 16가지의 종류가 존재하고, 세 사람의 심리적 거리를 구할 때, 3개 이상 동일한 MBTI가 존재하면 그 거리는 무조건 0으로 계산되므로, 비둘기집의 원리에 따라, 33개 이상의 MBTI가 주어지면 심리적 거리는 반드시 0으로 계산된다.

그 외의 경우에는 모든 경우의 수를 구해서 계산이 가능한데, 제한사항을 고려하더라고 최악의 경우가 $32*31*30/6 = 4960$이므로 충분히 제한사항을 지키며 계산 가능하다.

# 가장 가까운 세 사람의 심리적 거리
import sys
from itertools import combinations
input = sys.stdin.readline
t=int(input().strip())
for _ in range(t):
    n=int(input().strip())
    lst = input().strip().split()
    res = []
    # 비둘기집 원리
    if len(lst)>32: # 중복되는 MBTI 3개 이상되는 경우
        print(0)
    else: # 그렇지 않은 경우, Brute Force(모든 경우의 수 구하기) : 최대 32C
        for i in combinations(lst,3):
            a,b,c = i
            diff = 0
            diff+=len(set(list(a))-set(list(b)))
            diff+=len(set(list(b))-set(list(c)))
            diff+=len(set(list(a))-set(list(c)))
            res.append(diff)
        print(min(res))