백준 20529번 가장 가까운 세 사람의 심리적 거리 - C++ 풀이

---

 

1. 33명의 사람을 16개의 mbti로 분류하는 경우, 최소한 한 mbti에는 반드시 3명이상 속하게 된다.
2. 32명 초과인 경우 심리적 거리의 최솟값은 0이다.
3. 32명 이하인 경우 심리적 거리의 최솟값은 브루트포스로 구할 수 있다.

 

1. 33명의 사람을 16개의 mbti로 분류하는 경우, 최소한 한 mbti에는 반드시 3명이상 속하게 된다.

 비둘기집의 원리란 "n+1 마리의 비둘기가 n개의 비둘기 집에 나누어들어간다면, 적어도 한 집에는 반드시 두 마리 이상의 비둘기가 들어가게 된다"는 원리이다. 이것을 현재 문제에도 적용할 수 있다. 사람 = 비둘기, mbti 종류 = 비둘기집으로 생각하면 된다. mbti가 16종류가 있으므로, 만약 사람이 16+1=17명 있다면, 적어도 한 mbti에는 반드시 2명 이상이 속하게 된다. 더 확장해서 사람이 16*2+1=33명 있다면, 적어도 한 mbti에는 반드시 3명 이상이 속하게 된다.

 

2. 32명 초과인 경우 심리적 거리의 최솟값은 0이다.

 32명 초과인 경우 한 mbti에는 반드시 3명이상 속하게 된다. 이때 해당 mbti에 속하는 3명, 즉 같은 mbti를 가진 3명을 뽑으면 심리적 거리는 0이 된다. 따라서 32명 초과인 경우, 무조건 심리적 거리를 0으로 만들 수 있다.

 

3. 32명 이하인 경우 심리적 거리의 최솟값은 브루트포스로 구할 수 있다.

 반대로 32명 이하인 경우, N명 중 3명을 뽑는 모든 경우를 고려하여 최솟값을 찾아주면 된다. N = 2^5로 매우 작기 때문에 O(N^3)의 시간복잡도도 충분하다.

---

#include <iostream>
#include <vector>

using namespace std;

const int INF = 8;

// 세 mbti의 심리적 거리를 구하는 함수
int calcDist(string a, string b, string c) {
    int diff = 4;
    
    for (int i=0; i<4; i++) {
        if (a[i] == b[i] && b[i] == c[i]) diff--;
    }
    
    // 세 명이 일치하지 않는 타입 하나마다 거리가 2씩 증가하므로
    return 2 * diff;
}

int calcMinDist(vector<string>& mbtis) {
    int min_dist = INF;
    int n = (int)mbtis.size();
    
    if (n > 32) {
        // Pigeonhole Principle에 의해
        // (16*2 + 1)명의 사람을 16개의 mbti로 분류하는 경우,
        // 최소한 한 mbti에는 반드시 3명이상 속하게 된다.
        min_dist = 0;   // 같은 mbti인 3명의 심리적 거리는 0
    }
    else {
        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 dist = calcDist(mbtis[i], mbtis[j], mbtis[k]);
                    min_dist = min(min_dist, dist);
                }
            }
        }
    }
    
    return min_dist;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int T;
    cin >> T;
    
    while (T--) {
        int N;
        cin >> N;
        
        vector<string> mbtis(N);
        for (int i=0; i<N; i++) cin >> mbtis[i];
        
        cout << calcMinDist(mbtis) << "\n";
    }
}