[Pytnon | 백준] 20529번: 가장 가까운 세 사람의 심리적 거리

문제 요약

MBTI 성격 유형을 가진 학생들 사이의 심리적인 거리를 계산하는 문제이다. 주어진 학생들 중 가장 가까운 세 학생의 심리적인 거리를 구하는 것이 목표이다.

입력

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

출력

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

 

풀이 설명

이 문제는 세 학생의 MBTI 유형 간의 심리적 거리를 구하는 문제이다. MBTI는 4개의 척도로 구성되어 있으므로 총 16개의 유형이 있다. 세 학생 간의 심리적 거리는 세 유형 간의 심리적 거리의 합으로 정의된다.

문제에서 비둘기집 원리를 적용하면 ( N > 32 )일 경우 최소한 두 명 이상의 학생이 같은 MBTI 유형을 가지게 된다. 따라서 세 학생을 선택했을 때 심리적 거리가 0인 경우가 반드시 존재하게 된다.

 

비둘기집 원리 (Pigeonhole Principle)

비둘기집 원리란 수학의 기초적인 원리 중 하나로, 매우 직관적이면서도 강력한 도구이다. 이 원리는 다음과 같이 설명할 수 있다:

• 비둘기집 원리: ( n )개의 비둘기를 ( m )개의 비둘기집에 넣을 때, 만약 ( n > m )이라면 최소한 하나의 비둘기집에는 두 개 이상의 비둘기가 들어가게 된다.

이 원리는 매우 단순해 보이지만, 다양한 수학적 문제와 컴퓨터 과학 문제에서 유용하게 사용된다.

 

문제에서의 비둘기집 원리 적용

주어진 문제에서 비둘기집 원리를 어떻게 적용할 수 있는지 자세히 설명하겠다.

1. 문제의 상황:
   • 학생들의 MBTI 유형이 주어진다.
   • 각 MBTI 유형은 4개의 문자로 이루어지며, 각 문자는 두 가지 선택지 중 하나이다.
   • 따라서 가능한 MBTI 유형의 총 수는 ( 2^4 = 16 )가지이다.
2. 비둘기집 원리 적용:
   • 만약 학생 수 ( N )이 33명 이상이라면, 비둘기집 원리에 따라 적어도 한 유형의 MBTI를 가진 학생이 두 명 이상 존재하게 된다.
   • 이는 가능한 MBTI 유형의 총 수가 16이므로, 33명 이상의 학생이 있다면 어떤 MBTI 유형은 최소 두 번 이상 나타날 수밖에 없다는 것을 의미한다.
   • 이 경우, 같은 MBTI 유형을 가진 세 명을 찾는 것이 가능하므로, 이들의 심리적 거리는 0이 된다. 이는 세 사람이 모두 동일한 MBTI 유형을 가질 때 그 거리의 합이 0이기 때문이다.

 

구체적인 예

• 예제:
  • 만약 MBTI 유형이 각각 다음과 같은 17명의 학생이 있다고 하자: ISTJ, ISFJ, INFJ, INTJ, ISTP, ISFP, INFP, INTP, ESTP, ESFP, ENFP, ENTP, ESTJ, ESFJ, ENFJ, ENTJ, ISTJ.
  • 여기서 가능한 MBTI 유형은 16가지이다. 그러나 17명이 있으므로, 적어도 한 유형의 MBTI는 두 번 나타나게 된다. 이 예제에서는 ISTJ 유형이 두 번 나타난다.
  • 따라서, 적어도 두 명의 ISTJ 유형 학생이 존재하게 된다. 만약 ( N > 32 )라면, 세 명 이상의 학생이 동일한 MBTI 유형을 가질 수밖에 없으며, 이 경우 그들의 심리적 거리는 0이 된다.

 

결론

비둘기집 원리는 이 문제에서 학생 수 ( N )이 33명 이상일 때 어떤 유형의 MBTI라도 중복해서 나타나는 것을 보장해 준다. 따라서 ( N )이 33 이상인 경우, 세 명의 학생이 동일한 MBTI 유형을 가질 가능성이 확실하며, 그들의 심리적 거리는 0으로 계산될 수 있다. 이는 문제의 특수한 경우를 빠르게 처리할 수 있는 중요한 포인트이다.

 

def count_dis(mbti1, mbti2):
    """ 두 MBTI 유형 사이의 거리를 계산하는 함수 """
    return sum(1 for a, b in zip(mbti1, mbti2) if a != b)

def find_minimum_distance(N, students):
    if N > 32:
        return 0  # 비둘기집 원리에 의해 같은 MBTI 유형이 반드시 존재

    min_distance = float('inf')
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(j + 1, N):
                dis_ij = count_dis(students[i], students[j])
                dis_jk = count_dis(students[j], students[k])
                dis_ik = count_dis(students[i], students[k])
                total_distance = dis_ij + dis_jk + dis_ik
                if total_distance < min_distance:
                    min_distance = total_distance
    return min_distance

T = int(input().strip())
for _ in range(T):
    N = int(input().strip())
    students = input().strip().split()
    print(find_minimum_distance(N, students))

코드 설명

1. 거리 계산 함수:두 MBTI 유형 간의 심리적 거리를 계산하는 함수이다. 각 문자 위치에서 다른 문자의 개수를 센다.

def count_dis(mbti1, mbti2): return sum(1 for a, b in zip(mbti1, mbti2) if a != b)

 

2. 최소 거리 찾기 함수:세 학생을 선택하여 심리적 거리를 계산하는 함수이다. ( N )이 32를 초과하면 비둘기집 원리에 의해 같은 유형을 가지는 학생이 반드시 존재하므로, 결과는 0이다. ( N )이 32 이하일 때 모든 가능한 세 학생의 조합을 탐색하며 최소 거리를 찾는다.

def find_minimum_distance(N, students):
    if N > 32:
        return 0  # 비둘기집 원리에 의해 같은 MBTI 유형이 반드시 존재

    min_distance = float('inf')
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(j + 1, N):
                dis_ij = count_dis(students[i], students[j])
                dis_jk = count_dis(students[j], students[k])
                dis_ik = count_dis(students[i], students[k])
                total_distance = dis_ij + dis_jk + dis_ik
                if total_distance < min_distance:
                    min_distance = total_distance
    return min_distance