[백준 20529] 가장 가까운 세 사람의 심리적 거리 (파이썬 풀이)

https://www.acmicpc.net/problem/20529

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

제출 코드

# 비둘기집 원리 

import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(input().split())
    if n>32:
        print(0)
    else:    
        ans = 100000
        p = []

        def dfs(start):
            global ans
            if len(p)==3:
                temp = 0
                for i in range(4):
                    if(p[0][i]!=p[1][i]):
                        temp +=1
                    if(p[1][i]!=p[2][i]):
                        temp +=1
                    if(p[2][i]!=p[0][i]):
                        temp +=1
                ans = min(ans,temp)
                return
            for i in range(start,n):
                p.append(arr[i])
                dfs(i+1)
                p.pop()
        dfs(0)
        print(ans)

브루트포스 알고리즘 문제지만, 조합을 사용하기 때문에 입력값이 많아지면 시간초과가 된다.

이 때 주목해야할 점은 MBTI는 16가지 밖에 없다는 점이다. MBTI가 16가지이므로 16명이 모이면 각기 다른 MBTI를 가진 사람들이 모일 수 있지만 17명부터는 무조건 두명 이상이 MBTI가 겹칠 수 밖에 없다. 이 문제에서는 3명씩 계산하므로 MBTI 종류별로 2명씩 총 32명에 한명이 추가되면 무조건 세명 이상이 MBTI가 겹쳐 학생들의 심리적 거리는 0이 나올 수 밖에 없다. 그러므로 33명부터는 무조건 답이 0이다. 이를 비둘기집 원리라고 한다.

 

비둘기집 원리 : n+1개의 물건을 n개의 상자에 넣은 경우, 최소한 한 상자에는 그 물건이 반드시 두 개 이상 들어있다는 원리

 

파이썬에서는 조합 라이브러리가 존재하기 때문에 그걸 사용해서 풀 수도 있다. 나는 재귀함수를 써서 구현하였다.