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

분류 : 비트 연산, 백트래킹 /

 

문제

문제 링크

문제 설명

여러분은 요즘 유행하는 심리검사인 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는 총 24=16$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, C$가 있을 때 이들의 심리적인 거리는

(A$A$와 B$B$ 사이의 심리적인 거리) + (B$B$와 C$C$ 사이의 심리적인 거리) + (A$A$와 C$C$ 사이의 심리적인 거리)

로 정의한다.

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

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

입력

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

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

출력

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

 

풀이

#include <iostream>
using namespace std;
const int MAX_ANS = 8, MBTI_KIND = 16, GROUP_SIZE = 3;
const char HASH_MAP[] = {'E', 'N', 'T', 'J'};

int N, ans;
int MBTI[2*MBTI_KIND];
int group[GROUP_SIZE];

int min(const int &a, const int &b) {return a < b ? a : b;}
int getHashedMBTI() {
    int hashed = 0;
    for(int i=0; i<4; i++) {
        char c; cin >> c;
        hashed <<= 1;
        if(c == HASH_MAP[i]) hashed++;
    }
    return hashed;
}
int bitCount(int x) {
    int n = 0;
    while(x > 0) {
        if(x & 1) n++;
        x >>= 1;
    }
    return n;
}
int getDist() {
    int dist = 0;
    for(int i = 0; i < GROUP_SIZE; i++)
        dist += bitCount(group[i] xor group[(i+1) % GROUP_SIZE]);
    return dist;
}
void backTracking(int cur, int len) {
    if(ans < 2) return;
    if(len == GROUP_SIZE) {
        ans = min(ans, getDist());
        return;
    }
    for(int i = cur; i <= N - GROUP_SIZE + len; i++) {
        group[len] = MBTI[i];
        backTracking(i+1, len+1);
    }
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    while(T--) {
        cin >> N;
        ans = (N > 2*MBTI_KIND) ? 0 : MAX_ANS;
        int freq[MBTI_KIND] = {};
        for(int i=0; i<N; i++) freq[getHashedMBTI()]++;
        for(int i=0, k=0; i<MBTI_KIND and ans; i++) {
            if(freq[i] == 0) continue;
            if(freq[i] > 2) ans = 0;
            else while(freq[i]--) MBTI[k++] = i;
        }
        backTracking(0, 0);
        cout << ans << '\n';
    }
}

 

• 3명 이상인 MBTI가 적어도 하나있다면 답은 0이다.
  • N이 32보다 크다면 3명 이상인 MBTI가 반드시 하나 이상 존재한다.(`비둘기집 원리`)
    • `ans = (N > 32) ? 0 : MAX_ANS`
  • `if( freq[i] > 2 ) ans = 0`
• 답이 0이 아닌경우(모든 MBTI가 3개 미만이고 N이 32 이하) 백트래킹으로 완전탐색
  • 이 경우 `MBTI`배열은 길이 `N`(32이하) 중복 최대 2개의 모든 MBTI

 

`getHashedMBTI` 함수는 입력받은 MBTI를 0과 15사이 숫자로 해싱 (`ISFP = 0000(2)` ~ `ENTJ = 1111(2)`)

`getDist`함수는 백트래킹으로 선택된 3개의 MBTI(`group`) 사이 거리의 합을 계산

두 MBIT의 거리는 해시값의 `XOR`연산 결과의 1의 개수로 계산 (`distBetweenAandB = bitCount(A xor B)`)

`bitCount`함수는 2진수에서 1의 숫자를 셈