백준 20529 - 가장 가까운 세 사람의 심리적 거리 [C/C++] MBTI

20529번: 가장 가까운 세 사람의 심리적 거리 (acmicpc.net)

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

문제 설명은 다음과 같다.

문제 설명 / 입력 / 출력

제한 / 예제 입력 / 예제 출력

 

상당히 신선한 문제이다.

요 근래 화제가 되고 있는 MBTI 테스트 관련 설명을 문제로 출제해서 개인적으로 재밌었던 문제 중 하나이다.

 

처음에는 한 큐에 어떻게 모든 케이스를 구현할 수 있을까 계속 머리를 굴려보다가 조금 시간을 많이 보냈는데, 알고 보니 이 문제는 상당히 중요한 원리를 놓치면 답이 없었다.

 

이 문제는 "비둘기집의 원리"를 이용해야 하는 문제이다. 

 

비둘기집의 원리란 간단히 말하자면, 비둘기 집이 9개가 있고, 비둘기가 10마리가 있다면, 반드시 한 집에는 2마리 이상의 비둘기가 들어갈 수 밖에 없다는 원리이다.

 

알다시피 MBTI는 4개의 영역을 2가지의 경우의 수로 나누는 것이므로, 최대 16가지의 경우의 수가 존재한다.

 

헌데 입력값으로 만약에 33개 이상의 MBTI가 들어온다면? 어느 한 MBTI는 반드시 "3개" 이상이 입력받았음이 보장된다 (비둘기집의 원리의 의해 : 비둘기집이 16개고, 비둘기가 33마리인 상황. 반드시 3마리 이상은 한 집에 들어간다.)

 

따라서 입력 케이스는 10만개가 최대지만, 사실 33개 초과의 값이 들어온다면 바로 0을 뱉어버리면 된다!

-> 시간초과를 매우 효과적이고 직관적으로 피할 수 있다.

 

3~32 사이의 값이 들어왔다면? 이제 그냥 일일이 3개를 뽑아가며 다른 것의 수를 세주면 된다. 시간복잡도가 확 줄어드니 이 정도 연산은 가뿐히 빠르게 해낼 수 있다.

 

아래는 제출한 C++ 코드이다.

#include <algorithm>
#include <iostream>
#include <vector>
#define fastcpp ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
int test_case, num;
string MBTI;
vector<string> v;
int main() {
    fastcpp;
    cin >> test_case;
    while (test_case>0){
        test_case--;
        cin >> num;
        if (num>32) {
            cout << 0 << '\n';
            cin.ignore();
            string s;
            getline(cin, s);
        }
        else {
            v = vector<string>();
            int minV = 12;
            for(int i=0;i<num;i++){
                cin >> MBTI;
                v.push_back(MBTI);
            }
            for (int i=0;i<num-2;i++){
                for (int j=i+1;j<num-1;j++){
                    for (int k=j+1;k<num;k++){
                        int cnt = 0;
                        for(int c=0;c<4;c++){
                            if (v[i][c]!=v[j][c]) cnt++;
                            if (v[j][c]!=v[k][c]) cnt++;
                            if (v[k][c]!=v[i][c]) cnt++;
                        }
                        minV = min(minV, cnt);
                    }
                }
            }
            cout << minV << '\n';
        }

    }
    return 0;
}