[Baekjoon] 20529_가장 가까운 세 사람의 심리적 거리

Silver I

문제(출처: https://www.acmicpc.net/problem/20529)

---

< 가장 가까운 세 사람의 심리적 거리 >

 

문제 풀이 

 

조합을 사용하여 3명의 학생의 MBTI 성격 유형을 뽑아 가장 가까운 세 사람의 심리적 거리를 구한다.

 

조합으로만 문제를 구현할 경우 시간초과가 발생한다. 시간을 줄일 방법을 몰라 찾아보니 비둘기집 원리를 사용하는 것이었다. 비둘기집 원리를 사용하면 MBTI가 총 16개 이므로 만약 사람 수가 32명이라면 똑같은 MBTI가 2명씩 있을 수 있으며 사람 수가 32명보다 많다면 똑같은 MBTI가 무조건 3명이 있게 된다. 그럼 가장 가까운 세 사람의 심리적 거리가 0이 되므로 사람 수가 32보다 크다면 조합을 구할 필요가 없다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class _20529_ { // 가장 가까운 세 사람의 심리적 거리
	static String arr[], result[];
	static int answer;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int t = Integer.parseInt(bf.readLine());

		for (int i = 0; i < t; i++) {
			int n = Integer.parseInt(bf.readLine());

			arr = new String[n];
			result = new String[n];
			answer = Integer.MAX_VALUE;

			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < n; j++) {
				arr[j] = st.nextToken();
			}

			if (n > 32) {
				answer = 0;
			} else {
				search(0, 0);
			}

			bw.write(answer + "\n");
		}
		bw.flush();
	}

	private static void search(int idx, int start) {
		if (idx == 3) {
			int temp = 0;
			for (int i = 0; i < 4; i++) {
				if (result[0].charAt(i) != result[1].charAt(i)) {
					temp += 1;
				}
				if (result[1].charAt(i) != result[2].charAt(i)) {
					temp += 1;
				}
				if (result[0].charAt(i) != result[2].charAt(i)) {
					temp += 1;
				}
			}
			answer = Math.min(temp, answer);
			return;
		}
		for (int i = start; i < arr.length; i++) {
			result[idx] = arr[i];
			search(idx + 1, i + 1);
		}
	}
}

변수)
t : 테스트 케이스 수
n : 학생의 수
arr : 학생의 MBTI
result : 조합으로 구한 3명의 MBTI
answer : 가장 가까운 세 사람의 심리적 거리

 

테스트 케이스 수, 학생의 수, 학생의 MBTI를 입력받아 저장한다. 학생의 수가 32보다 크다면 가장 가까운 세 사람의 심리적 거리가 0이다. 32보다 크지 않다면 조합을 구하기 위해 search 함수를 호출한다.

 

search 함수를 통해 조합으로 3명을 뽑는다. 만약 조합으로 3명을 다 구했다면 A와 B 사이의 심리적인 거리, B와 C 사이의 심리적인 거리, A와 C 사이의 심리적인 거리를 구한 후 가장 가까운 세 사람의 심리적 거리를 구한다.

---

---