백준 20529번 문제 바로가기

문제 상황 이해

한때 핫했던 MBTI를 활용한 재밌는 문제. MBTI 글자 하나가 다를때마다 거리를 1로 잡고 그 거리의 총합을 구하는 문제다.

Keypoint

  • 비둘기집의 원리을 활용해서 if문 작성해주기
  • MBTI의 총 가짓수가 2^4=16종류이기 때문에 33명 이상이면 반드시 3명은 같은 MBTI를 가진다
def distance(case):
    temp = 0
    for i in range(3):
        for j in range(4):
            if case[i%3][j] != case[(i+1)%3][j]:
                temp += 1
    return temp


n_test = int(input())
for i in range(n_test):
    n_friend = int(input())
    mbti = input().split()
    if n_friend >= 33:
        print(0)
    else:
        min_distance = 20
        for x in range(n_friend-2):
            for y in range(x+1, n_friend-1):
                for z in range(y+1, n_friend):
                    d = distance([mbti[x], mbti[y], mbti[z]])
                    if d < min_distance:
                        min_distance = d
        print(min_distance)

#include <iostream>
#include <string>

using namespace std;

int distance(string a, string b, string c){
    int temp = 0;
    for (int i=0; i<4; i++){
        if (a[i] != b[i]){
            temp++;
        }
        if (b[i] != c[i]){
            temp++;
        }
        if (c[i] != a[i]){
            temp++;
        }
    }
    return temp;
}

int main() {
    int n_test, n_friend;
    string name;
    string mbti[100000];
    cin >> n_test;
    for (int i=0; i<n_test; i++){
        int d, min_distance = 20;
        cin >> n_friend;
        for (int j=0; j<n_friend; j++){
            cin >> name;
            mbti[j] = name;
        }
        if (n_friend >= 33){
            cout << 0 << endl;
        } else {
            for (int x=0; x<n_friend-2; x++){
                for (int y=x+1; y<n_friend-1; y++){
                    for (int z=y+1; z<n_friend; z++){
                        d = distance(mbti[x], mbti[y], mbti[z]);
                        if (d < min_distance){
                            min_distance = d;
                        }
                    }
                }
            }
            cout << min_distance << endl;
        }
    }
}