BOJ-20529 가장 가까운 세 사람의 심리적 거리

https://www.acmicpc.net/problem/20529

문제 소개

테스트 케이스의 수 T가 주어지고 각 테스트 케이스마다 학생의 수 N과 N명의 학생의 MBTI 성격 유형이 주어진다.

각 테스트 케이스에 대하여 주어진 N 명중 가장 가까운 세 학생 사이의 심리적인 거리를 구한다.

두 사람 사이의 심리적인 거리는 두 사람의 MBTI 유형에서 서로 다른 분류에 속하는 척도의 수이다.

세 사람 A, B, C가 있을 때 이들의 심리적인 거리는 (A와 B사이의 심리적인 거리) + (B와 C사이의 심리적인 거리) + (A와 C사이의 심리적인 거리) 이다.

문제 풀이

주어지는 성격을 bitset 라이브러리를 사용하여 4비트로 나타내어 비교가 간편하도록 하였다.

함수 cal()은 3개의 성격을 입력으로 받아 세 사람 사이의 심리적인 거리를 계산한다.

각 테스트케이스마다 n명 중 3명을 뽑아서 나오는 심리적인 거리 중 최소값을 구한다.

이때 만약 n명의 학생 중 성격이 똑같은 학생이 3명 이상이라면 가장 가까운 세 학생 사이의 심리적인 거리는 0이 된다.

여기까지만 생각해서 답을 제출하면 시간 초과에 걸리게 된다. (생각해 보면 n의 값이 최대 10만인데 3명씩 뽑을 수 있는 모든 경우의 수를 고려하니 당연한 결과다)

잠시 생각해보면 성격의 종류는 총 16가지이며, 비둘기집의 원리에 의하여 n이 16보다 크다면 적어도 한 종류의 성격은 한 명보다 많은 수를 가진다는 것을 알 수 있다.

그렇다면 성격이 똑같은 학생이 3명이 될 수 있는 n의 최솟값은 얼마인지 생각해보면 간단히 33임을 알 수 있다.

그 이유는 최대한 겹치는 성격이 없도록 입력을 32명 받았을 때를 생각해 보면 알 수 있다. 이는 모든 성격 유형이 2명씩 있는 경우이며, 여기서 어떤 성격 유형이든 1명을 받게 되면 특정 성격유형이 3명이 된다. 즉, n >= 33이라면 결과는 0으로 고정이다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <bitset>

char mbti[4] = { 'E', 'S', 'T', 'J' };

typedef std::bitset<4> mbti_t;

// 세 사람의 심리적인 거리를 계산하는 함수
int cal(mbti_t x, mbti_t y, mbti_t z) {
	int acc = 0;
	for (int i = 0; i < 4; i++) {
		if (x[i] != y[i]) {
			acc += 1;
		}
		if (x[i] != z[i]) {
			acc += 1;
		}
		if (y[i] != z[i]) {
			acc += 1;
		}
	}
	return acc;
}

int main() {
	using namespace std;
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int t;
	cin >> t;

	while (t--) {
		int n;
		cin >> n;
		vector<mbti_t> arr;
		for (int i = 0; i < n; i++) {
			string t;
			cin >> t;

			mbti_t x;
			for (int j = 0; j < 4; j++) {
				if (t[j] == mbti[j]) {
					x[j] = 1;
				}
			}

			arr.push_back(x);
		}

        // n이 32보다 크다면 성격 유형이 똑같은 사람이 최소 3명 이상 존재하게 된다
		if (n >= 33) {
			cout << 0 << "\n";
			continue;   // 다음 테스트 케이스로 진행
		}

		int min = 12;
		for (int i = 0; i < n - 2; i++) {
			for (int j = i + 1; j < n - 1; j++) {
				for (int k = j + 1; k < n; k++) {
					int t = cal(arr[i], arr[j], arr[k]);
					if (t < min) {
						min = t;
					}
				}
			}
		}
		cout << min << "\n";
	}

	return 0;
}