문제 요약
MBTI 성격 유형을 가진 학생들 사이의 심리적인 거리를 계산하는 문제이다. 주어진 학생들 중 가장 가까운 세 학생의 심리적인 거리를 구하는 것이 목표이다.
입력
- 첫 줄에는 테스트 케이스의 수를 나타내는 정수 ( T )가 주어진다.
- 각 테스트 케이스의 첫 줄에는 학생의 수를 나타내는 정수 ( N )이 주어지며, 두 번째 줄에는 각 학생의 MBTI 성격 유형을 나타내는 문자열들이 공백을 두고 주어진다.
출력
각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다.
풀이 설명
이 문제는 세 학생의 MBTI 유형 간의 심리적 거리를 구하는 문제이다. MBTI는 4개의 척도로 구성되어 있으므로 총 16개의 유형이 있다. 세 학생 간의 심리적 거리는 세 유형 간의 심리적 거리의 합으로 정의된다.
문제에서 비둘기집 원리를 적용하면 ( N > 32 )일 경우 최소한 두 명 이상의 학생이 같은 MBTI 유형을 가지게 된다. 따라서 세 학생을 선택했을 때 심리적 거리가 0인 경우가 반드시 존재하게 된다.
비둘기집 원리 (Pigeonhole Principle)
비둘기집 원리란 수학의 기초적인 원리 중 하나로, 매우 직관적이면서도 강력한 도구이다. 이 원리는 다음과 같이 설명할 수 있다:
- 비둘기집 원리: ( n )개의 비둘기를 ( m )개의 비둘기집에 넣을 때, 만약 ( n > m )이라면 최소한 하나의 비둘기집에는 두 개 이상의 비둘기가 들어가게 된다.
이 원리는 매우 단순해 보이지만, 다양한 수학적 문제와 컴퓨터 과학 문제에서 유용하게 사용된다.
문제에서의 비둘기집 원리 적용
주어진 문제에서 비둘기집 원리를 어떻게 적용할 수 있는지 자세히 설명하겠다.
- 문제의 상황:
- 학생들의 MBTI 유형이 주어진다.
- 각 MBTI 유형은 4개의 문자로 이루어지며, 각 문자는 두 가지 선택지 중 하나이다.
- 따라서 가능한 MBTI 유형의 총 수는 ( 2^4 = 16 )가지이다.
- 비둘기집 원리 적용:
- 만약 학생 수 ( 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이 된다.
- 만약 MBTI 유형이 각각 다음과 같은 17명의 학생이 있다고 하자:
결론
비둘기집 원리는 이 문제에서 학생 수 ( 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