[백준/BOJ][C++] 20529번 : 가장 가까운 세 사람의 심리적 거리(비둘기집 원리)

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

문제

각 척도마다 두 가지 분류가 존재하므로, 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 <= T <= 50
• 3 <= N <= 100000
• 각 테스트 케이스의 N의 합은 100000을 넘지 않는다.

접근 방법

<브루트 포스?>

세 사람의 심리적 거리를 구하는 데 특별한 방법이 생각나지 않았고, 브루트 포징을 하자니 N의 최댓값이 100000인 점을 고려하면, 최대 100000C3(조합)의 작업이 소요된다.

 

여기서 주목해야 할 점은 MBTI는 총 16가지밖에 없다는 것이다. 즉 32명이 넘어가는 순간 어쩔 수 없이 똑같은 MBTI를 가진 사람이 최소 3명이 나오게 된다. 그렇게 되면 가장 가까운 세 학생 사이의 심리적인 거리는 0이 되기 때문에 N > 32일 때는 모두 0으로 간주해도 무방하다.

 

<비둘기집 원리>

• 정의 : n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어있다.

위에서 설명한 로직은 비둘기집 원리의 로직과 같다. 따라서 이 문제는 비둘기집 원리로 범위를 줄인 후에 브루트 포징을 실행한다.

브루트 포스 방식일 때, 시간초과가 날 것 같으면 비둘기집 원리를 한번 생각해 보자.

주의할 점

N = 32일 때까지 0으로 간주하면 안 된다.

코드

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

using namespace std;

int dist(string a, string b){ //a와 b의 심리적 거리 구하기
	int ans = 0;
	for(int i = 0; i < 4; i++){
		if(a[i] != b[i])
			ans++;
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	for(int i = 0; i < t; i++){
		vector<string> v;
		int n;
		cin >> n;
		for(int j = 0; j < n; j++){
			string str;
			cin >> str;
			v.push_back(str);
		}
		if(n > 32){ //비둘기집 원리
			cout << "0\n";
			continue;
		}
		int real = 20; //임의의 큰값. 이보다 큰 값은 나올 수 없음
		for(int j = 0; j < n - 2; j++){
			for(int m = j+1; m < n - 1; m++){
				for(int k = m + 1; k < n; k++){
					real = min(real, dist(v[j], v[m]) + dist(v[m], v[k]) + dist(v[j], v[k]));
				}
			}
		}
		cout << real << "\n";
	}
}