[BOJ 20529 / C++] 가장 가까운 세 사람의 심리적 거리

백준 문제 링크 : 20529 - 가장 가까운 세 사람의 심리적 거리

문제

여러분은 요즘 유행하는 심리검사인 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명의 사람들 가운데서 3명을 고르되, 가장 심리적 거리가 최소인 경우를 구하는 문제

따라서 브루트포스 알고리즘으로 이를 확인하려면, for문을 3중으로 중첩하여 모든 세 사람 조합을 구하면 되는데.. 당연히도 O(n^3) 스케일이니 주어진 제한범위 내에서는 시간초과가 날 수 밖에 없습니다.

이 때 비둘기집 원리를 적용하는게 중요한데, 비둘기집 원리란..

• n+1개의 물건을 n개의 상자에 넣을 경우, 최소한 한 상자에는 그 물건이 반드시 두 개 이상 들어있다!

라는 원리입니다.. 흥미롭네요~

이 문제의 경우로 생각해 보면,

MBTI유형은 16가지니까, 사람이 16명보다 많으면, 즉 17명 이상이라면? 무조건 두 명은 MBTI 유형이 같습니다.

그럼 이제 사람이 33명 이상이라면? 최소한 어떤 하나의 유형은 무조건 세 명 이상 있습니다

따라서 n > 32일 경우 무조건, 가장 가까운 심리적 거리는 0입니다.

때문에 확인해야 할 범위가 32까지 확 줄어들었고, 이제 브루트포스 알고리즘으로 모두 확인해봐도 시간 걱정은 없습니다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int mbtiCheck(string m1, string m2, string m3) {
	int result = 0;
	for(int i=0;i<4;i++) {
		if (m1[i] != m2[i]) result++;
	}
	for(int i=0;i<4;i++) {
		if (m1[i] != m3[i]) result++;
	}
	for(int i=0;i<4;i++) {
		if (m2[i] != m3[i]) result++;
	}
	return result;
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	for(int c=0;c<t;c++) {
		int n;
		cin >> n;
		string *mbti = new string[n];
		for(int j=0;j<n;j++) {
			cin >> mbti[j];
		}
		if (n > 32) cout << "0\n";
		else {
			int d = -1;
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					for(int k=0;k<n;k++) {
						if (i == j || j == k || i == k) continue;
						int tmp = mbtiCheck(mbti[i], mbti[j], mbti[k]);
						if (d == -1 || tmp < d) d = tmp; 
					}
				}
			}
			cout << d << "\n";
		}
	}
}

둘 풍 당 당