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

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

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

문제 한줄 이해

-요즘 유행하는 MBTI로 사람간의 심리적 거리를 계산한다. ENFJ와 ISFP가 있을때 심리적 거리는 3! 이때 주어진 사람들 중 3명의 값이 제일 작은 경우 구하기

생각난 풀이

1번째 방법: 리스트에 사람들을 담아 백트래킹을 통해 심리적 거리를 갱신 해주자! 이때 mbti의 갯수는 총 16개 그렇다면 사람이 33명이 들어오면 무조건 심리적 거리는 0임을 생각하자 why? 최악의 경우를 생각하면 32 명안에 2,2,2,2,2,2.... 이렇게 mbti가 같은 사람이 구성 될거다 그럼 여기서 한명이 더 추가 된다면 누가 들어오던 겹치는 사람이 3명이 생긴다. 이런 경우는 심리적 거리가 0이기에 탐색을 하지 않는다.

import sys

t = int(sys.stdin.readline())

def dfs(start):
    global ans
    if len(three) == 3:
        cnt = 0
        for i in range(2):
            for j in range(i+1,3):
                if three[i][0] != three[j][0]:
                    cnt +=1
                if three[i][1] != three[j][1]:
                    cnt +=1
                if three[i][2] != three[j][2]:
                    cnt +=1
                if three[i][3] != three[j][3]:
                    cnt +=1
        if ans > cnt:
            ans = cnt
        return
    
    for i in range(start,n):
        three.append(mbti[i])
        dfs(i+1)
        three.pop()

for _ in range(t):
    n = int(sys.stdin.readline())
    if n >=33:
        ans = 0
        mbti = list(map(str, sys.stdin.readline().split()))
    else:
        mbti = list(map(str, sys.stdin.readline().split()))
        three = []
        ans = 1e9
        dfs(0)
    print(ans)