[백준 #20529 c++] 가장 가까운 세 사람의 심리적 거리, Brute Force

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

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

실버 1이라고 얕보다간 큰 코 다치는 문제이다.
본인은 이 문제를 보고 처음에는 Brute Force로 시도했지만 시간초과, 이후 DP로 시도해보려 했는데 예외가 발생해서 실패를 겪었다.
 
첫번째 풀이: 평범한 Brute Force(시간초과)

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

int dist(string a, string b) {
	int cnt = 0;
	for (int i = 0; i < a.size(); i++) {
		if (a[i] != b[i]) cnt++;
	}
	return cnt;
}


int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int t;
	cin >> t;

	for (int i = 0; i < t; i++) {
		int n;
		cin >> n;
		vector<string> v(n);
		vector<int> com(n); com[0] = com[1] = com[2] = 1;
		for (int j = 0; j < n; j++) {
			cin >> v[j];
		}

		int minV = 1e9;

		do {
			int tmp[3];
			int idx = 0;
			for (int j = 0; j < com.size(); j++) {
				if (com[j] == 1) {
					tmp[idx++] = j;
				}
			}
			int m = dist(v[tmp[0]], v[tmp[1]]) + dist(v[tmp[1]], v[tmp[2]]) + dist(v[tmp[0]], v[tmp[2]]);
			if (minV > m) minV = m;
		} while (prev_permutation(com.begin(), com.end()));
		cout << minV << '\n';
	}
}

3중 반복문 대신 순열 또는 조합을 구할 때 사용하는 prev_permutation을 이용했다.
당연하지만 시간초과가 난다.
그 이유는 학생의 최대 인원 수는 100,000명이고 이 경우 3명을 뽑는 조합의 개수는 166조를 넘어가기 때문에 일반적인 Brute Force가 아니다.
 
두번째 풀이: DP(불가능)

	int t;
	cin >> t;

	for (int i = 0; i < t; i++) {
		int n;
		cin >> n;
		vector<string> v(n + 1);
		vector<pair<vector<int>, int>> dp(n + 1, make_pair(vector<int>(3), 0));

		cin >> v[1] >> v[2] >> v[3];
		dp[3] = { {1,2,3}, dist(v[1], v[2]) + dist(v[2], v[3]) + dist(v[1], v[3]) };

		for (int j = 4; j <= v.size(); j++) {
			cin >> v[j];
		}

		cout << dp[n].second << '\n';
	}

n번째 학생까지의 최소 심리적 거리를 구할때에는 n-1번째 학생까지의 최소 심리적 거리에 해당하는 학생들의 번호와 n번째 학생을 비교하여 계산하면 된다는 생각으로 코드를 짰지만,
새로운 유형의 학생을 만날 때마다 전혀 다른 조합의 학생으로 최소 심리적 거리가 나온다는 예외가 나오는걸 발견하고 바로 멈추었다.
 
 
결국 해설지를 보게 됐고 비둘기집 원리라는 것을 처음 알게 됐다.
 
비둘기집 원리는 쉽게 말해,
100개의 비둘기 집이 있고 101마리의 비둘기를 이 집들에 나누어 넣을 때
최소한 하나의 집에는 2마리 이상의 비둘기가 존재해야 한다는 얘기다.
이는 추가 설명할 필요도 없이 매우 직관적이다.
 
이를 문제에 적용하면,
17명의 학생이 모였을 때 최소한 2명의 MBTI가 같게 된다.
그 이유는 MBTI의 유형은 16개이고 학생이 그 수보다 많게 되면 유형의 개수를 초과하기 때문이다.
 
학생 수가 17명부터 32명까지인 경우,
여기에는 MBTI가 겹치는 학생이 최소 2명이 있고 이 두 명의 심리적 거리는 0이 된다.
그리고 나머지 한 명과 비교하게 되면 선택된 모든 학생의 MBTI가 같아서 심리적 거리의 합이 0이 되거나,
정반대 MBTI를 가진 학생과 만나서 심리적 거리의 합이 0 + 4 + 4 = 8이 될 수 있다.
즉, 최소 심리적 거리는 0~8 사이의 값이 된다.
 
학생 수가 33명부터 48명까지인 경우,
여기에는 MBTI가 겹치는 학생이 최소 3명이 있게 된다.
그 이유는, 1번부터 16번까지의 MBTI가 다 다르고 17번부터 32번까지의 MBTI가 다 달라도 두 명의 학생끼리 같은 MBTI를 가지게 되며,
마지막 33번 학생과 만나는 순간 모두 같은 MBTI를 가지는 학생 3명이 반드시 모이게 된다.
 
이 말인 즉슨, 학생수가 33명 이상이 되는 순간부터 최소 심리적 거리가 0이 된다.
 
이 중요한 사실을 코드에 적용해보면
 
 
세번째 풀이: Brute Force + 예외처리(통과)

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

int dist(string a, string b) {
	int cnt = 0;
	for (int i = 0; i < a.size(); i++) {
		if (a[i] != b[i]) cnt++;
	}
	return cnt;
}


int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int t;
	cin >> t;

	for (int i = 0; i < t; i++) {
		int n;
		cin >> n;
		vector<string> v(n);
		vector<int> com(n); com[0] = com[1] = com[2] = 1;
		for (int j = 0; j < n; j++) {
			cin >> v[j];
		}

		if (n >= 33) {
			cout << 0 << '\n';
			continue;
		}

		int minV = 1e9;

		do {
			int tmp[3];
			int idx = 0;
			for (int j = 0; j < com.size(); j++) {
				if (com[j] == 1) {
					tmp[idx++] = j;
				}
			}
			int m = dist(v[tmp[0]], v[tmp[1]]) + dist(v[tmp[1]], v[tmp[2]]) + dist(v[tmp[0]], v[tmp[2]]);
			if (minV > m) minV = m;
		} while (prev_permutation(com.begin(), com.end()));
		cout << minV << '\n';
	}
}

n이 33 이상일 때 0을 반환하도록 하는 코드만 넣었을 뿐인데 통과가 되었다.
 

여기서 시간을 조금 더 줄이려면
prev_permutation 대신 3중 반복문을 사용하고
dist 함수 내부를 개조해서 3개의 인자를 받고 4개의 문자를 순회하면서 다음 연산을 거치도록 바꾸면 된다.
 
cnt += (a[i] != b[i]) + (b[i] != c[i]) + (a[i] != c[i]);
 

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

int dist(string a, string b, string c) {
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
		cnt += (a[i] != b[i]) + (b[i] != c[i]) + (a[i] != c[i]);
	}
	return cnt;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int t;
	cin >> t;

	for (int tc = 0; tc < t; tc++) {
		int n;
		cin >> n;

		vector<string> v(n);
		for (auto& i : v) {
			cin >> i;
		}

		if (n >= 33) {
			cout << 0 << '\n';
			continue;
		}

		int ans = 1e9;

		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				for (int k = j + 1; k < n; k++) {
					ans = min(ans, dist(v[i], v[j], v[k]));
				}
			}
		}

		cout << ans << '\n';
	}
}

 
실버 1이라서 그동안 학습해온 유형대로만 적용하면 된다고 생각했는데, 아니었다.
문제의 유형만 보고 바로 코드를 적지말고 문제에 대해 조금 더 고민하고 보다 창의적인 생각을 해야한다고 알려주는 문제였다.