[이산수학] 비둘기집 원리

n개의 비둘기 집에 n+1마리 이상의 비둘기가 들어갔다면, 두 마리 이상의 비둘기가 들어간 집이 적어도 하나 있음

 

특정 조건을 만족하는 요소의 존재를 증명할 때 사용

 

문제) 백준 20529번 가장 가까운 세 사람의 심리적 거리

import sys
from itertools import combinations
input = sys.stdin.readline

def distance(A, B):
    cnt = 0
    for x, y in zip(A, B):
        if x!=y:
            cnt += 1
    return cnt

T = int(input())
for _ in range(T):
    N = int(input())
    mbti = input().split()

    if N>32:
        print(0)
    else:
        result = []
        for x, y, z in combinations(mbti, 3):
            result.append(distance(x,y)+distance(y,z)+distance(x,z))
        print(min(result))