[백준 20529번] 가장 가까운 세 사람의 심리적 거리 (C++)

문제링크 : https://www.acmicpc.net/problem/20529

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
vector<string>v;

int cal(string s1, string s2, string s3) //3개 문자열 비교
{
    int result = 0;
    for(int i=0; i<4; i++)
    {
        result+=(s1[i] != s2[i]) + (s2[i] != s3[i]) + (s1[i] != s3[i]); //각 문자가 다를때마다 카운트
    }   
    return result;
}

int func() //3개 최소합 저장
{
    if(N>32) return 0;
    int result = MAX;
    for(int i=0; i<N; i++)
    {
        for(int j=i+1; j<N; j++)
        {
            for(int k=j+1; k<N; k++)
            {
                result = min(result, cal(v[i], v[j], v[k]));
            }
        }
    }
    return result;
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int T;
    cin >> T;
    while(T--)
    {
        cin >>N;
        v.resize(N);
        for(int i=0; i<N; i++)
        {
            cin >> v[i];
        }
        cout << func() << "\n";
    }
    
    return 0;
}

기본적으로 브루트포스로 풀었다.

근데 MBTI의 종류를 보면 16개인 것을 알 수 있고, 비교하는 MBTI는 3가지이다.

MBTI 3가지가 모두 같으면 무조건 0을 출력하므로 만약 N의 갯수가 32개를 넘어서면 출력은 무조건 0인 것을 알 수 있다.

왜냐하면 16개씩 2번해서 모든 MBTI가 2번씩 중복되었고, 이후에 나오는 MBTI는 무조건적으로 3번째 중복이 발생하기 때문이다.

따라서 33번째부터 나오는 MBTI는 그게 무엇이든 간에 3번째 중복을 발생시키므로 0을 출력하게 된다.

 

나머지 값에 따라서는 3중 for문으로 모든 케이스를 확인했다.

그리고 각 문자열의 문자 길이를 또 비교하여 각 문자열의 문자들이 서로 다를때마다 카운트를 해주고 이를 더해준다.

3중 for문을 통해 위 작업을 모든 케이스에 대해 확인하며 가장 작은 값을 반환해주면 된다.