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

SILVER I

 

문제

여러분은 요즘 유행하는 심리검사인 MBTI에 대해 들어보았는가?

MBTI(Myers-Briggs Type Indicator)는 C.G.Jung의 심리유형론을 근거로 하여 Katharine Cook Briggs와 Isabel Briggs Myers가 보다 쉽고 일상생활에 유용하게 활용할 수 있도록 고안한 자기보고식 성격유형지표이다. (출처: 위키백과)

MBTI는 아래와 같이 네 가지 척도로 사람들의 성격을 구분한다.

 

외향(E) / 내향(I)
감각(S) / 직관(N)
사고(T) / 감정(F)
판단(J) / 인식(P)

 

각 척도마다 두 가지 분류가 존재하므로, MBTI는 총 $2^4 = 16$가지 유형이 있음을 알 수 있다. 일반적으로 MBTI의 유형들은 각 분류를 나타내는 알파벳 한 글자씩을 따 네 글자로 표시하게 된다. 모든 유형의 목록은 다음과 같다.

 

ISTJ, ISFJ, INFJ, INTJ, ISTP, ISFP, INFP, INTP, ESTP, ESFP, ENFP, ENTP, ESTJ, ESFJ, ENFJ, ENTJ

 

MBTI 성격 유형을 이용하면 두 사람 사이의 심리적인 거리를 정의할 수 있다. 이는 두 사람의 MBTI 유형에서 서로 다른 분류에 속하는 척도의 수로 정의된다. 예를 들어, MBTI 유형이 ISTJ인 사람과 ISFJ인 사람 사이의 거리는 1이며, INTP인 사람과 ENTJ인 사람 사이의 거리는 2이다.

이 정의를 확장해서 세 사람 사이의 심리적인 거리도 정의할 수 있다. 세 사람
$A, B, C$가 있을 때 이들의 심리적인 거리는

 

($A$와 $B$ 사이의 심리적인 거리) + ($B$와 $C$ 사이의 심리적인 거리) + ($A$와 $C$ 사이의 심리적인 거리) 로 정의한다.

 

대학교에서 심리학 교수로 일하는 종서는 자신이 가르치는 학생들의 심리적인 특성을 분석하고 싶어한다.

오늘이 생일인 종서를 위해 $N$명의 학생들의 MBTI 유형이 주어질 때, 가장 가까운 세 학생 사이의 심리적인 거리를 구해보자.

 

입력

첫 줄에는 테스트 케이스의 수를 나타내는 정수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 학생의 수를 나타내는 하나의 정수 $N$이 주어지며, 두 번째 줄에는 각 학생의 MBTI 성격 유형을 나타내는 문자열들이 사이에 공백을 두고 주어진다.

 

출력

각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다.

 

풀이

주어진 mbti 중에서 세 개를 고르는 것이기에, 백트래킹을 이용해 모든 경우의 수를 비교하는 브루트포스 방식으로 접근했다.

 

하지만 이렇게 하면 n이 10만일 경우 반드시 시간 초과가 일어날 수밖에 없다. 시간을 단축시킬 방법을 찾아야 했으나 고민해보아도 떠오르지 않아 문제의 '알고리즘 분류'를 확인해보았다.

알고리즘 분류
- 브루트포스 알고리즘
- 비둘기집 원리

 

비둘기집 원리? 알고리즘 시간에 잠깐 배운 기억은 있으나 잘 떠오르지 않아서 검색해보니,

n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리

 

라고 한다.

 

이 문제를 기준으로 했을 때, mbti는 총 16가지가 존재하므로 17명의 사람이 있으면 적어도 두 명은 같은 mbti를 가진다는 뜻이다.

 

이 원리를 활용하면, 같은 mbti끼리의 심리적 거리는 0이므로 같은 mbti를 가진 인물이 3명이 있으면 이 문제의 해는 반드시 0이 된다는 것을 알 수 있다.

if(n >= 33){
    printf("0\n");
    continue;
}

 

따라서 학생의 수가 33명 이상으로 주어졌을 때, (그러니까 n >= 33) 브루트포스를 하지 않고 0을 출력해주면 된다.

그러면 시간 초과 없이 문제를 해결할 수 있다.

전체 코드

#include <stdio.h>
#include <stdlib.h>

void backtracking(int, int);
int dist;

int n;
char mbti[100000][4];

int main() {
    int t;
    scanf("%d", &t);


    for (int i = 0; i < t; i++) {
        scanf("%d", &n);        
        getchar();

        for (int k = 0; k < n; k++) {
            for (int j = 0; j < 4; j++)
                mbti[k][j] = getchar();
            getchar();
        }

        if(n >= 33){
            printf("0\n");
            continue;
        }

        dist = __INT_MAX__;
        backtracking(0, 0);
        printf("%d\n", dist);
    }

    return 0;    
}

int tmp[3];
void backtracking(int cnt, int start) {
    if(cnt == 3){
        int sum = 0;
        for (int  i = 0; i < 4; i++) {
            if (mbti[tmp[0]][i] != mbti[tmp[1]][i])
                sum++;
            if (mbti[tmp[1]][i] != mbti[tmp[2]][i])
                sum++;
            if (mbti[tmp[0]][i] != mbti[tmp[2]][i])
                sum++;
        }        

        dist = dist < sum ? dist : sum;
        return;
    }

    for (int i = 0; i < n; i++) {
        if(start <= i){
            tmp[cnt] = i;
            backtracking(cnt + 1, i+1);
       }
    }
}