[Good Bye, BOJ 2020!] B.가장 가까운 세 사람의 심리적 거리

 이제 두 번째 문제다. 이 문제는 해결 시간보다 문제를 이해하는 시간이 더 오래 걸렸다.

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

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

 처음에는 가장 가까운 연속된 세 사람의 심리적 거리인 줄 알았다.

하지만 사람들 중에 세 사람을 뽑아서 그들의 거리를 중 가장 가까운 사람을 뽑는다는 것을 깨달았다.

 

 

 

 파이썬 combinations를 써서 될 수 있는 조합을 다 만든다. 그리고 그 조합들을 하나하나를 set으로 바꿔 차집합의 길이를 계산한다.

세 사람의 거리를 다 리스트에 넣고 가장 작은 것을 출력한다.

하지만 조합은 nCr 이기 때문에 시간 초과가 났다.

나로써는 여기에서 더 줄일 방법이 생각나지 않아서 곰곰히 생각해봤다.

비둘기집의 원리를 이용하면 16*3 이상의 입력은 무의미하다.

이산수학에서 배운 비둘기집의 원리가 생각이 났다. 

 

적어도 어느 한 상자에는 두 마리 이상의 비둘기가 있다.

 

비둘기집의 원리 : n + 1개의 비둘기를 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다.

이 원리를 문제에 적용해보자. (16*3+1) 이상의 사람이 입력되면, 적어도 MBTI가 똑같은 사람이 3명 이상 있다.

나는 49명을 기준으로 해서 이 이상 초과하면 (적어도 세 명의 MBTI가 같으므로) 0을 출력하게 식을 작성했다.

 

from collections import deque
from itertools import combinations
 
def diff(x, y, z):
    p1 = set(list(x))
    p2 = set(list(y))
    p3 = set(list(z))
    return len(p1.difference(p2)) + len(p2.difference(p3)) + len(p3.difference(p1))
 
for _ in range(int(input())):
    num = int(input())
    student = list(input().split())
    if num >= 49:
        print(0)
    else:
        com = list(combinations(student, 3))
        answer = deque([])
        for i in com:
            answer.append(diff(i[0], i[1], i[2]))
        print(min(answer))

 

B문제를 풀면서 식을 작성할 때, 입력, 출력과 조건을 이해하는 것이 우선임을 느꼈다.

1학기 이산수학에서 배운 지식을 활용해서 뿌듯했다!