[백준] 20529번 : 가장 가까운 세 사람의 심리적 거리 (C++)

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

---

문제)

여러분은 요즘 유행하는 심리검사인 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 사이의 심리적인 거리) + (B와 C 사이의 심리적인 거리) + (A와 C 사이의 심리적인 거리)

로 정의한다.

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

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

 

 

 

입력 :

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

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

 

 

 

출력 :

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

 

 

 

 

풀이)

 

// 20259. 가장 가까운 세 사람의 심리적 거리
 
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <climits>
 
using namespace std;
 
int t, n;
map<string, int> m;
vector<string> vec;
int ans;
 
int diff(vector<string>& vec)
{
    int total = 0;
    for (int i = 0; i < 2; i++)
    {
        for (int j = i + 1; j < 3; j++)
        {
            for (int k = 0; k < 4; k++)
            {
                if (vec[i][k] != vec[j][k]) total++;
            }
        }
    }
 
    return total;
}
 
void recur(int cur, vector<string>& vec)
{
    // MBTI가 3개라면 심리적인 거리를 계산하고
    // 그중 제일 최소값을 ans에 저장한다.
    if (cur == 3)
    {
        ans = min(ans, diff(vec));
        return;
    }
 
    // 해당 MBTI가 0 이상이라면 해당 MBTI를 가지고 다음 루프로 진입한다.
    for (map<string, int>::iterator iter = m.begin(); iter != m.end(); iter++)
    {
        if (iter->second > 0)
        {
            iter->second--;
            vec.push_back(iter->first);
            recur(cur + 1, vec);
            vec.pop_back();
            iter->second++;
        }
    }
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> t;
 
    while (t--)
    {
        cin >> n;
        m.clear();
        ans = INT_MAX;
 
        // MBTI의 종류를 MAP에 저장한다.
        string a;
        for (int i = 0; i < n; i++)
        {
            cin >> a;
            m[a]++;
        }
 
        recur(0, vec);
 
        cout << ans << '\n';
    }
}
 

---

출처 : https://www.acmicpc.net/problem/20529 

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