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

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

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

 

솔루션

---

비둘기 집을 이용하여 문제를 해결해야 했다.

 

비둘기 집은 경우의 수가 K개이고  입력이 K 를 초과하면 무조건 중복되는 값이 존재한다는 뜻이다.

 

처음에 생각하기에 MBTI가 16가지이므로 , 16~31, 32~ 47, 48 ~...

이렇게 나눌려고 했었지만, 코드로 짜기에는 너무 귀찮았다.

 

그런데, 입력이 48 이상인 경우는 무조건 0이 되고,

나머지는 48C3 이므로 충분히 돌아갈 것이라 생각을 했고, 그냥 48미만이면 완전 탐색으로 해결하였다.

 

48개 미만이면, N과M 처럼 3개를 고르고 점수 계산을 하고 최소 값을 리턴 하도록 하였다.

 

 

코드

---

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<string> V;
vector<string> ans;

int calc(void) {
	int cnt = 0;
	for (int i = 0; i < ans.size() - 1; i++) {
		for (int j = i + 1; j < ans.size(); j++) {
			for (int k = 0; k < 4; k++) {
				if (ans[i][k] != ans[j][k]) {
					cnt++;
				}
			}
		}
	}
	return cnt;
}

int solve(int deep, int idx) {
	if (deep == 3) {
		return calc();
	}
	else {
		int ref = 987654321;
		for (int i = idx; i < V.size(); i++) {
			ans.push_back(V[i]);
			ref = min(ref, solve(deep + 1, i + 1));
			ans.pop_back();
		}
		return ref;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	
	int tc;
	cin >> tc;
	while (tc--) {
		V.clear();

		cin >> N;
		for (int i = 0; i < N; i++) {
			string str;
			cin >> str;

			V.push_back(str);
		}

		if (N >= 48) {
			cout << 0 << '\n';
		}
		else {
			cout << solve(0, 0) << '\n';
		}
	}
}