[백준] 14889번 : 스타트와 링크 - JAVA [자바]

안녕하세요.

오늘은 [백준] 14889번 : 스타트와 링크 문제를 풀어보도록 하겠습니다.

 

 

📌 접근

1. 팀 나누기 - 조합 탐색

• 사람들을 두 팀으로 나누는 모든 조합을 탐색해야 합니다.
• 단, [start: 1, 2], [link: 3, 4] 와 [start: 3, 4], [link: 1, 2] 는 사실상 같은 조합입니다.
• 그래서 0번째 사람은 항상 start팀에 포함시키도록 고정하면 불필요한 연산을 절반으로 줄일 수 있습니다.

2. 능력치 차이 계산

• 조합이 완성되면, 두 팀의 능력치를 구합니다.
• 팀의 구성원 쌍을 순회하며 arr[i][j] + arr[j][i]를 더합니다.
• 차이가 최솟값이라면 갱신합니다.

 

💻 풀이

// hyeblee
import java.util.*;
import java.io.*;


public class Main {
  
  public static int n; // 전체 사람 수
  public static int[][] arr; // 능력치 저장 배열
  public static boolean[] isStart; // start팀에 속하는지 여부
  public static int min = Integer.MAX_VALUE;

  public static void combi(int idx, int count) {
    if (count == n / 2) { // start팀에 속하는 사람이 n/2일때만 두 팀의 능력치 차이 계산
      diff();
      return;
    }

    for (int i = idx; i < n; i++) {
      isStart[i] = true;
      combi(i + 1, count + 1);
      isStart[i] = false;
    }
  }

  public static void diff() {
    int start = 0;
    int link = 0;

    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        if (isStart[i] && isStart[j]) { // i와 j가 start팀인 경우
          start += arr[i][j] + arr[j][i];
        } else if (!isStart[i] && !isStart[j]) { // j와 i가 start팀인 경우
          link += arr[i][j] + arr[j][i];
        }
      }
    }

    int diff = Math.abs(start - link);
    min = Math.min(diff, min);
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());

    arr = new int[n][n];
    isStart = new boolean[n];

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

    isStart[0] = true; // 0번째 사람은 항상 start팀
    combi(1, 1);
    System.out.println(min);

  }
}

 

🤔 고민했던 점 & 어려웠던 부분

요즘 알고리즘별로 문제를 풀어보고 있어서, 백트래킹 문제라는 것은 알고 있었습니다.

또한 i번째 사람을 start팀으로 선택해보고, 정답이 아니면 선택하지 않는 방식으로 구현해야한다는 것까지 생각했습니다.

 

하지만 이것들이 어려웠습니다.

1. 두 팀으로 나누는 조합을 어떻게 계산할 것인가?
2. 팀의 조합이 바뀔 때마다, 이중 for문으로 능력치를 계산하면 시간초과가 나지 않을까?

 

❓ Q1. 두 팀으로 나누는 조합은 어떻게 구할까?

• 브루트포스 방식으로 조합을 전부 탐색합니다.
• 단, N/2명이 선택된 시점에서만 능력치 차이를 계산합니다.
• 0번 사람을 무조건 start팀에 포함시켜 중복 조합을 줄이는 게 핵심입니다.

❓ Q2. 조합마다 능력치를 2중 for문으로 계산하면 시간초과 안 날까?

• 보통 1초에 약 1억 연산이 가능하다고 추정합니다.
• 이 문제의 경우,
  • 20명 중 10명 선택 → 약 92,378개의 조합
  • 각 조합마다 팀 쌍 계산 (10명 팀 → 45쌍) → 약 90번 연산
  • 총 연산량 ≈ 92,378 × 90 = 약 8백만
• → 넉넉하게 2초 안에 해결 가능합니다!