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

문제 보기

20529 실버1

💡 생각

일단 콤비네이션으로 3개를 뽑고, compare 함수로 그 3개의 mbti 거리를 측정한다음
mn 값과 비교해줘서 최소값을 출력하게 했다.

🖥️ 소스코드

#define fastio ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <string.h>
using namespace std;

/* Method Initialization */
void combi(int start, vector<int> b);
int compare(string str1, string str2, string str3);
/* Variable Initialization */
int n, t;
string str;
vector<string> mbtis;
int mn;
map<string, int> m;

int main()
{
    cin >> n;
    for(int i = 0 ; i < n; i++)
    {
        mbtis.clear();
        m.clear();
        mn = 1e7;
        cin >> t;
        for(int j = 0; j < t ; j++)
        {
            cin >> str;
            m[str]++;
            mbtis.push_back(str);
        }
        if (t > 32){
            cout << 0 << '\n';
            continue;
        }
        if(m[str] == 3){
            cout << 0 << '\n';
            continue;
        }
        vector<int> b;
        combi(-1, b);
        cout << mn << '\n';
    }
    return 0;
}

void combi(int start, vector<int> b)
{
    int tmp;
    if(b.size() == 3)
    {
        tmp = compare(mbtis[b[0]], mbtis[b[1]], mbtis[b[2]]);
        mn = min(tmp, mn);
        return;
    }
    for(int i = start + 1; i < mbtis.size(); i++)
    {
        b.push_back(i);
        combi(i, b);
        b.pop_back();
    }
    return;
}

int compare(string str1, string str2, string str3)
{
    int tmp = 0;
    for(int i = 0; i < 4; i++)
    {
        if(str1[i] != str2[i]) tmp++;
        if(str1[i] != str3[i]) tmp++;
        if(str2[i] != str3[i]) tmp++;
    }
    return tmp;
}

그런데 흐음
계속 시간초과가 나서 어디서 나나... 봤는데
이미 mbti가 같은 것이 3개 나왔을 경우 / mbti가 33개 이상 있을 경우
는 무조건 답이 0이 나와야 한다.
이래서 시간초과가 난다. 문제에서 주어진 테케 수가 100000 넘어갈 때도 있으니까
딱 32 초과면 0으로 끊어주고 continue.. 이런 식으로 해야했다

map으로 3개 나오면 0 으로 하게 해줬고 조건문으로 조건 명시해줬다!