문제
풀이
- N이 100000으로 하나하나 비교하면 시간초과
- MBTI의 종류는 16가지로 서로 최대한 MBTI가 다르도록 배치한다면 N이 16일 때, 모두가 다른 MBTI를 가진다.
- N이 16을 초과한 경우에 최대한 MBTI가 다르도록 배치한다면 2명은 같은 MBTI를 가진다.
- 같은 원리로 N이 32를 초과한 경우에 최대한 MBTI르 다르도록 배치한다면 3명은 같은 MBTI를 가지므로 N이 32를 초과한다면 결과는 0이 된다.
- N이 32이하인 경우는 탐색이 필요하다.
코드
#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;
vector<string> MBTIs;
vector<string> mini_MBTIs;
int mini = INT_MAX;
// MBTI가 다른 자리마다 +1
int CalcDistance()
{
int distance = 0;
for (int i = 0; i < 3; ++i)
{
for (int j = i + 1; j < 3; ++j)
{
for (int k = 0; k < 4; ++k)
{
if (mini_MBTIs[i][k] != mini_MBTIs[j][k])
{
distance++;
}
}
}
}
return distance;
}
void BackTracking(int index)
{
if (mini_MBTIs.size() == 3)
{
mini = min(mini, CalcDistance());
return;
}
for (size_t i = index + 1; i < MBTIs.size(); ++i)
{
mini_MBTIs.push_back(MBTIs[i]);
BackTracking(i);
mini_MBTIs.pop_back();
}
}
int main()
{
int T;
cin >> T;
while (T--)
{
int N;
cin >> N;
// 사람 수가 32를 초과하면 무조건 MBTI가 3사람은 겹치기 때문에 결과는 0
if (N > 32)
{
string temp;
while (N--)
{
cin >> temp;
}
cout << 0 << endl;
}
else
{
while (N--)
{
string temp;
cin >> temp;
MBTIs.push_back(temp);
}
// 백트래킹으로 3사람을 추려 최소값을 탐색
for (size_t i = 0; i < MBTIs.size(); ++i)
{
mini_MBTIs.push_back(MBTIs[i]);
BackTracking(i);
mini_MBTIs.pop_back();
}
cout << mini << endl;
MBTIs.clear();
mini_MBTIs.clear();
mini = INT_MAX;
}
}
return 0;
}
