문제해결(PS)/백준(BOJ)

백준 20529 가장 가까운 세 사람의 심리적 거리 파이썬

곰탱이장 2024. 4. 18. 20:14

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

 

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

각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다.

www.acmicpc.net

문제가 처음 봤을때는 하나하나 비교하면 못해도 시간복잡도가 O(N^3)이라 시간초과에 걸릴 것이 딱 보였다. 하지만 문제 태그를 보니 비둘기집의 원리가 있는걸 보고 MBTI는 16개 밖에 없으니 사람이 33명 이상이라면 못해도 3명은 같은 MBTI라 심리적 거리가 0이 되는 경우가 있다는 걸 알게 되었다.

그러므로 N이 32 이하 일때만 무식하게 브루트포스로 구하고 그 33 이상이라면 그냥 0을 출력하게 만들었다.

import sys
input = sys.stdin.readline

T=int(input().rstrip())
for _ in range(T):
    N=int(input().rstrip())
    l=(input().rstrip()).split()
    if N>32:
        print(0)
    else:
        mi=10
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    if i==j or j==k or k==i:
                        continue
                    cnt=0
                    a,b,c=l[i],l[j],l[k]
                    for v in range(4):
                        if a[v]!=b[v]:
                            cnt+=1
                        if b[v]!=c[v]:
                            cnt+=1
                        if c[v]!=a[v]:
                            cnt+=1
                    if mi>cnt:
                        mi=cnt
        print(mi)