[Python] 백준 20529번 - 가장 가까운 세 사람의 심리적 거리 (실버 1)

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

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

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 수학
 - 브루트포스 알고리즘
 - 비둘기집 원리

 

문제

여러분은 요즘 유행하는 심리검사인 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 유형이 주어질 때, 가장 가까운 세 학생 사이의 심리적인 거리를 구해보자.

입력

첫 줄에는 테스트 케이스의 수를 나타내는 정수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 학생의 수를 나타내는 하나의 정수 $N$이 주어지며, 두 번째 줄에는 각 학생의 MBTI 성격 유형을 나타내는 문자열들이 사이에 공백을 두고 주어진다.

출력

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

제한

• $1 \le T \le 50$ 
•  $3 \le N \le 100\,000$ 
• 각 테스트 케이스의 $N$의 합은 $100\,000$을 넘지 않는다.

 

---

 

N이 최대 100,000까지라서 문뜩 드는 생각은

 

'모든 경우의 수를 다 확인했다간 무조건 시간 초과에 걸리겠다.'였다.

 

여기서 비둘기집 원리란

 

https://namu.wiki/w/%EB%B9%84%EB%91%98%EA%B8%B0%20%EC%A7%91%EC%9D%98%20%EC%9B%90%EB%A6%AC

비둘기 집의 원리 - 나무위키

 

이를 해당 문제에서 요약하자면

 

mbti는 경우의 수가 총 16가지이다.

 

이 중 문제는 가장 가까운 3가지 거리만을 요구하고 있다.

 

그렇다면 아무리 못해도 같은 mbti 3개가 나오려면 최소 몇 개여야 할까?

답은 33개부터 무조건 1가지 경우의 mbti는 3번 나온다는 것이다.

 

그럼 이제 문제는 조금 쉬워진다.

 

33 이상이면 거리는 무조건 0

 

32 이하이면 경우의 수를 확인하는 것이다.

 

import sys
input = sys.stdin.readline
from collections import deque

def cal(q):
    total = 0
    for i in range(2):
        for j in range(i+1, 3):
            for k in range(4):
                if q[i][k] != q[j][k]:
                    total += 1
    return total

def find(index, data):
    global total
    if len(q) == 3:
        now = cal(q)
        total = min(total, now)
        return
    for i in range(index, n):
        q.append(data[i])
        find(i+1, data)
        q.pop()

t = int(input())
for _ in range(t):
    n = int(input())
    data = list(map(str, input().split()))
    q = deque()
    total = int(1e9)
    if n > 32:
        print(0)
    else:
        find(0, data)
        print(total)

3개 묶음을 찾는 방법은 백트래킹을 이용하여 풀었다.