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

문제

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

풀이

문제 해석을 하자면,

• 오늘이 생일인 종서를 위해 N명의 학생들의 MBTI 유형이 주어질 때, 가장 가까운 세 학생 사이의 심리적인 거리를 구해보자.
• 심리적 거리 공식 : (A와 B 사이의 심리적인 거리) + (B와 C 사이의 심리적인 거리) + (A와 C 사이의 심리적인 거리)

풀이

• 조합을 사용해 N명중 3명을 선택하고 주어진 공식을 사용해 심리적 거리를 구해서 비교하자.
  • 단, 일반적으로 조합의 경우의수가 브루트포스 관점으로 보면 시간초과가 자명하다.
  • n이 10만일 때 _10만C₃ 의 값은 엄청 크기 때문이다.
• 이때, “비둘기집 원리” 가 필요하다.
  • 비둘기집 원리 : n+1개의 물건을 n개의 상자에 넣은 경우, 최소한 한 상자에는 그 물건이 반드시 두 개 이상 들어있다는 원리
  • 서로 다른 2개의 MBTI 는 16*2=32개가 한계이다. 그러므로 33개 부터는 무조건 동일한 MBTI 3개인 경우가 존재한다는 것이 핵심!
    • ₃₂C₃ = 4960 으로 조합 값도 크지않다! -> 시간여유
    • 따라서 n이 33개 이상일 경우 0을 출력하면 된다.

코드

static int N;
static int result;
static String[] inArr;
static int outArr[]; // N명중 3명 선택한 inArr의 index를 기록

static void check() {
    int diff = 0;
    String A = inArr[outArr[0]];
    String B = inArr[outArr[1]];
    String C = inArr[outArr[2]];
    for (int i = 0; i < 4; i++) {
        // A, B
        if (A.charAt(i) != B.charAt(i)) {
            diff++;
        }
        // B, C
        if (B.charAt(i) != C.charAt(i)) {
            diff++;
        }
        // A, C
        if (A.charAt(i) != C.charAt(i)) {
            diff++;
        }
    }
    result = Math.min(result, diff);
}

static void dfs(int depth, int idx) {
    //    if (result == 0) return; // 시간초과 방지 -> 이걸로도 해결 가능
    //base condition
    if (depth == 3) {
        check(); // 심리적 거리 계산함수
        return;
    }
    //recursion
    for (int i = idx; i < N; i++) {
        outArr[depth] = i;
        dfs(depth + 1, i + 1);
    }
}

public static void main(String[] args) throws IOException {
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());
    for (int t = 0; t < T; t++) {
        result = Integer.MAX_VALUE; //init
        outArr = new int[3]; //init
        N = Integer.parseInt(br.readLine());
        inArr = new String[N + 1];
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            inArr[i] = stk.nextToken();
        }
        //run
        if(N <= 32)
            dfs(0, 0);
        //output
        if (N <= 32)
            sb.append(result).append("\n");
        else
            sb.append(0).append("\n");
    }
    System.out.println(sb);
}

느낀점

비둘기집 원리라는 것을 기억해두자.