[브루트포스/비둘기집 원리] 백준 20529 가장 가까운 세 사람의 심리적 거리 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

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

 

 

 

2. 문제 풀이

 N명의 mbti가 주어질 때, 세 사람의 mbti 심리적 거리의 최소값을 구하는 문제입니다.

 mbti의 심리적 거리는 단순히 다른 개수입니다. (entp와 intp의 심리적 거리는 1)

 

 

반응형

 

3. 코드

from itertools import combinations
import sys
input = sys.stdin.readline

def mbti_dist(a, b):
    dist = 0
    for i, j in zip(a, b):
        if i != j:
            dist += 1
    return dist

T = int(input())
for _ in range(T):
    N = int(input())
    mbti = input().rstrip().split()
    
    res = 13    # 세 사람의 심리적인 거리
    case = combinations(mbti, 3)    # 세 명을 뽑을 조합
    for a, b, c in case:
        dist = 0
        dist += mbti_dist(a, b)
        dist += mbti_dist(b, c)
        dist += mbti_dist(a, c)
        
        res = min(res, dist)
    print(res)

 단순히 브루트포스로 구현하면 '시간 초과'가 납니다.

 

 

if N > 32:
	print(0)

 '비둘기집 원리'를 이용해야 하며, 꽤나 단순한 원리입니다.

 N개의 비둘기집에 N+1 비둘기가 있다면, 무조건 2마리 이상인 집이 있겠죠. 마찬가지로 mbti는 16가지이며, 17명이면 무조건 2명은 mbti가 겹칩니다. 그렇다면 33명이면 무조건 3명은 mbti가 겹치겠죠...

 그래서 N > 32이면 무조건 세 사람의 심리적 거리가 0이 됩니다. 

 

 

from itertools import combinations
import sys
input = sys.stdin.readline

def mbti_dist(a, b):
    dist = 0
    for i, j in zip(a, b):
        if i != j:
            dist += 1
    return dist

T = int(input())
for _ in range(T):
    N = int(input())
    mbti = input().rstrip().split()
    
    if N > 32:
        print(0)
    else:
        res = 13    # 세 사람의 심리적인 거리
        case = combinations(mbti, 3)    # 세 명을 뽑을 조합
        for a, b, c in case:
            dist = 0
            dist += mbti_dist(a, b)
            dist += mbti_dist(b, c)
            dist += mbti_dist(a, c)
            
            res = min(res, dist)
        print(res)

 비둘기집 원리를 반영하면 쉽게 통과됩니다.