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

 문제

3이상의 사람수에 대해 3명을 뽑아 두명끼리 비교하여 mbti가 다를때마다 +1을 더해 가장 적은 수가  나오는 경우를 구하는 문제이다!

 

---

풀이

모든 경우의 수를 분석하는 브루트 포스 알고리즘을 사용하여 풀었다.

for i in range(N):
            for j in range(N):
                for k in range(N):
                    tmp = 0
                    if i == j or j == k or k == i:
                        continue
                    for x in range(4):
                        if mbti[i][x] != mbti[j][x]:
                            tmp += 1
                        if mbti[j][x] != mbti[k][x]:
                            tmp += 1
                        if mbti[k][x] != mbti[i][x]:
                            tmp += 1
                    answer = min(answer, tmp)

3명을 뽑아야 하므로 3중 for문을 사용하였고, 자기 자신과 비교하면 안되므로 

 if i == j or j == k or k == i:

을 추가시켰다.

뽑은 3명에 대해 대해 각각의 mbti가 일치하지 않을경우 +1을 해주었고 가장 작은 결과값을 얻기위해 min을 사용하였다.

 

하지만 해당 풀이법은 시간초과가 뜬다!

 

좀 더 찾아보니 비둘기집 원리라는 알고리즘이 있었다.

MBTI의 종류는 총 16가지이기 때문에 17명이 있으면 반드시 2명은 중복된 mbti를 가지고있고, 33명이 되면 3명은 반드시 같은 mbti인 경우가 생긴다. 따라서 n>33일경우에는 최종적으로 0만 출력해주면 된다. 해당 조건을 추가한 코드를 작성하였더니 문제가 풀렸다.

 

---

코드

T = int(input())
while T:
    answer = 999999
    T -= 1
    N = int(input())
    mbti = list(map(str, input().split()))

    if N > 32:
        print(0)
    else:
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    tmp = 0
                    if i == j or j == k or k == i:
                        continue
                    for x in range(4):
                        if mbti[i][x] != mbti[j][x]:
                            tmp += 1
                        if mbti[j][x] != mbti[k][x]:
                            tmp += 1
                        if mbti[k][x] != mbti[i][x]:
                            tmp += 1
                    answer = min(answer, tmp)
        print(answer)