[백준 C++] 20529 가장 가까운 세 사람의 심리적 거리 - 브루트포스

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

#include <iostream>
#include <string>
using namespace std;

string Students[32];

int GetDistance(string A, string B, string C)
{
	int Distance = 0;

	for (int i = 0; i < 4; ++i)
	{
		if (A[i] != B[i])
		{
			++Distance;
		}

		if (B[i] != C[i])
		{
			++Distance;
		}

		if (C[i] != A[i])
		{
			++Distance;
		}
	}

	return Distance;
}

void Test()
{
	int N;
	cin >> N;
	if (N > 32)
	{
		string Temp;
		for (int i = 0; i < N; ++i)
		{
			cin >> Temp;
		}

		cout << 0 << '\n';
		return;
	}

	for (int i = 0; i < N; ++i)
	{
		cin >> Students[i];
	}

	int MinDistance = 100;
	for (int A = 0; A < N - 2; ++A)
	{
		for (int B = A + 1; B < N - 1; ++B)
		{
			for (int C = B + 1; C < N; ++C)
			{
				MinDistance = min(MinDistance, GetDistance(Students[A], Students[B], Students[C]));
			}
		}
	}
	cout << MinDistance << '\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int T;
	cin >> T;
	for (int i = 0; i < T; ++i)
	{
		Test();
	}
}

---

 

학생 세 명을 선택해서 심리적인 거리를 구하는 작업을 전체 학생에 대해 모두 시도해봐야 하는 문제입니다.

하지만 이대로 바로 연산을 수행하면 O(N^3)의 시간 복잡도에 따라 N의 크기가 커졌을 때 시간 초과가 발생하게 됩니다.

 

이에 대한 해결책으로 MBTI의 유형이 총 16가지라는 점에서 풀이 방법을 유추할 수 있습니다.

전체 학생이 32명이 넘어가면 같은 MBTI를 가진 학생은 무조건 최소 세 명 이상임을 알 수 있습니다.

이때 심리적인 거리의 최소값은 0이 되므로 따로 비교 연산을 수행하지 않아도 됩니다.

 

1. N의 크기가 33 이상일 때, 바로 0을 출력하도록 로직 구현

2. N의 크기가 32 이하일 때, 전체 학생에 대해 각각 비교하는 작업을 수행