백준 20529 - 가장 가까운 세 사람의 심리적 거리(C++)

문제 링크입니다. https://www.acmicpc.net/problem/20529

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

경우를 나눈 뒤, 경우에 해당하는 방식으로 푸는 문제입니다.

16개의 mbti를 중복이 가능하게 주어졌을 때, 3명의 심리적 거리를 구하는 문제입니다.
심리적 거리를 구하는 방법은 4개의 알파벳 중, 다른게 있을 때마다 1씩 늘어나게 됩니다.

여기서 N값이 주어질 때, 100,000개까지 주어집니다. 따라서 100,000개를 전부 확인해본다면 무조건 시간 초과가 생길 것입니다.

따라서, 시간을 줄일 방법을 찾아야하는데,
만약에 N이 17개가 주어졌다고 한다면, 16개의 mbti가 전부 주어진 뒤, 중복된 것 하나가 추가로 주어진다는 의미입니다. -> 최소 2개 이상이 겹치게 됩니다.
N이 33개라면 16개 2번씩, 중복된 것 1개 해서, 3개가 항상 겹친다는 의미입니다. -> 이때는 심리적 거리가 항상 0이 나오게 됩니다.

그렇다면, N이 33개 이상이라면, 경우를 구할 필요가 없이 항상 0을 출력하면 되며, N이 33개 미만일 경우만 확인하면 된다는 의미입니다.

N이 32개 이하이면, 모든 경우를 확인해도 시간초과는 생기지 않으니, 완전탐색을 통해 확인해주면 됩니다.



자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#define INF 987654321

using namespace std;

int test_case;
int N;
string arr[100001];
int ans;

int diffrent_mbti(int x, int y, int z){
	int sum = 0;
	for(int i = 0; i < 4; i++){
		if(arr[x][i] != arr[y][i]) sum++;
		if(arr[x][i] != arr[z][i]) sum++;
		if(arr[y][i] != arr[z][i]) sum++;
	}
	return sum;
}

void select_mbti(){
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			for(int k = 1; k <= N; k++){
				if(i == j || j == k || i == k) continue;
				ans = min(ans, diffrent_mbti(i, j, k));
				if(ans == 0) return;
			}
		}
	}
}

void solve(){
	ans = INF;
	select_mbti();
	cout << ans << "\n";
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> test_case;
	for(int i = 1; i <= test_case; i++){
		cin >> N;
		for(int j = 1; j <= N; j++){
			cin >> arr[j];
		}
		if(N >= 33) {
			cout << "0" << "\n";
			continue;
		}
		solve();
	}
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.