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

문제 & 링크

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

 

 

풀이

1. 입력 및 출력의 개수가 많기에 빠른 입출력을 사용한다.

2. MBTI의 개수는 16개이기에 비둘기집 정리에 의해 N이 33개 이상이면 무조건 같은 MBTI 3개가 나온다. 따라서 N이 33개 이상일 때는 답을 0으로 출력해준다.

3. N의 개수를 100,000개에서 최대 32개로 줄였으니, 백트래킹을 사용하여 MBTI 조합을 찾아준다. 이때 depth를 사용하여 현재 조합 내에 있는 MBTI의 개수를 판단해준다.

4. depth가 3일 경우 심리적 거리를 계산해준다.

5. 계산식은 E_cnt * I_cnt + S_cnt *  N_cnt +  T_cnt * F_cnt + J_cnt * P_cnt이다.

6. 심리적 거리의 최솟값을 알아야 하기에 min을 사용하여 답을 구한다. 백트래킹이 끝나면 최종 답을 출력해준다.

 

코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int N;
vector<string> V;
int ans = 10;
vector<string> three_people(3);

void back_tracking(int depth, int idx) {
    if (depth == 3) {
        int E_cnt = 0, S_cnt = 0, T_cnt = 0, J_cnt = 0;
        for (int i = 0; i < 3; i++) {
            if (three_people[i][0] == 'E') E_cnt++;
            if (three_people[i][1] == 'S') S_cnt++;
            if (three_people[i][2] == 'T') T_cnt++;
            if (three_people[i][3] == 'J') J_cnt++;
        }
        
        int sum = E_cnt * (3 - E_cnt) + S_cnt * (3 - S_cnt) + T_cnt * (3 - T_cnt) + J_cnt * (3 - J_cnt);
        
        ans = min(ans, sum);
        return;
    }
    
    for (int i = idx; i < N; i++) {
        three_people[depth] = V[i];
        back_tracking(depth + 1, i + 1);
    }
}

int main() {
    // 빠른 입출력
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    
    int T;
    cin >> T;
    
    while (T--) { 
        cin >> N;
        
        V = vector<string>(N); // N 크기의 벡터로 초기화
        ans = 10; // 8 초과는 절대 나오지 않음
        
        for (int i = 0; i < N; i++) {
            cin >> V[i];
        }
        
        if (N > 32) cout << 0 << "\n"; // 비둘기집 정리에 의해 33부터 무조건 같은 MBTI 3개가 나옴
        else {
            back_tracking(0, 0);
        
            cout << ans << "\n";
        }
        
        
    }
}