[Python]20529번.가장 가까운 세 사람의 심리적 거리(브루트포스)

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

💡문제

여러분은 요즘 유행하는 심리검사인 MBTI에 대해 들어보았는가?

MBTI(Myers-Briggs Type Indicator)는 C.G.Jung의 심리유형론을 근거로 하여 Katharine Cook Briggs와 Isabel Briggs Myers가 보다 쉽고 일상생활에 유용하게 활용할 수 있도록 고안한 자기보고식 성격유형지표이다. (출처: 위키백과)

MBTI는 아래와 같이 네 가지 척도로 사람들의 성격을 구분한다.

• 외향(E) / 내향(I)
• 감각(S) / 직관(N)
• 사고(T) / 감정(F)
• 판단(J) / 인식(P)

각 척도마다 두 가지 분류가 존재하므로, MBTI는 총 2^4 = 16가지 유형이 있음을 알 수 있다. 일반적으로 MBTI의 유형들은 각 분류를 나타내는 알파벳 한 글자씩을 따 네 글자로 표시하게 된다. 모든 유형의 목록은 다음과 같다.

• ISTJ, ISFJ, INFJ, INTJ, ISTP, ISFP, INFP, INTP, ESTP, ESFP, ENFP, ENTP, ESTJ, ESFJ, ENFJ, ENTJ

MBTI 성격 유형을 이용하면 두 사람 사이의 심리적인 거리를 정의할 수 있다. 이는 두 사람의 MBTI 유형에서 서로 다른 분류에 속하는 척도의 수로 정의된다. 예를 들어, MBTI 유형이 ISTJ인 사람과 ISFJ인 사람 사이의 거리는 1이며, INTP인 사람과 ENTJ인 사람 사이의 거리는 2이다.

이 정의를 확장해서 세 사람 사이의 심리적인 거리도 정의할 수 있다. 세 사람 A, B, C가 있을 때 이들의 심리적인 거리는

(A와 B사이의 심리적인 거리) + (B와 C사이의 심리적인 거리) + (A와 C사이의 심리적인 거리)

로 정의한다.

대학교에서 심리학 교수로 일하는 종서는 자신이 가르치는 학생들의 심리적인 특성을 분석하고 싶어한다.

오늘이 생일인 종서를 위해 N명의 학생들의 MBTI 유형이 주어질 때, 가장 가까운 세 학생 사이의 심리적인 거리를 구해보자.

 

 

• 첫 번째 테스트 케이스의 경우, ENTJ와 INTP의 심리적인 거리는 2, ENTJ와 ESFJ의 심리적인 거리는 2, INTP와 ESFJ의 심리적인 거리는 4이므로 세 사람의 심리적인 거리는 2+2+4=8이다.
• 두 번째 테스트 케이스의 경우, 어떤 사람 둘을 골라도 심리적인 거리가 0이므로 가장 가까운 세 사람의 심리적인 거리는 0이다.
• 세 번째 테스트 케이스의 경우, 심리적인 거리를 최소화하려면 MBTI가 ESTP, ESTJ, ISTJ인 세 사람을 골라야 한다. ESTP와 ESTJ의 심리적인 거리는 1, ESTP와 ISTJ의 심리적인 거리는 2, ESTJ와 ISTJ의 심리적인 거리는 1이므로 세 사람의 심리적인 거리는 1+2+1=4이다.

import sys
input = sys.stdin.readline
 
t = int(input())
 
while t:
    ans = 999999
    t -= 1
    n = int(input())
    a = 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 i == k:
                        continue
                    for x in range(4):
                        if a[i][x] != a[j][x]: tmp += 1
                        if a[j][x] != a[k][x]: tmp += 1
                        if a[i][x] != a[k][x]: tmp += 1
                    ans = min(tmp, ans)
        print(ans)

💡비둘기집 원리
(n+1)개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리
mbti는 총 16가지이기 때문에 17명이면 무조건 2명은 mbti가 겹친다.
즉, 33명이면 무조건 3명은 겹치기 때문에 n>32이 된다면 무조건 세 사람의 심리적 거리는 0이된다.