BOJ_14889 : 스타트와 링크

👉 문제링크

14889번: 스타트와 링크

---

---

🔸 문제 분석 🔸

• N명 중에서 N/2명을 뽑았을때 나오는 시너지 차이의 최소값을 출력한다.
• N명에서 N/2를 뽑는 조합 문제이다.
  • 반대 팀으로 뽑히면 같은 값을 중복으로 검사하게 되지만, 시간복잡도가 허용범위 내이므로 감안해도 된다.
  • 조합으로 뽑아 시너지 차이의 최소값을 업데이트한다.

🔸 코드 🔸

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

public class Main {
    private static int N, ans = Integer.MAX_VALUE;
    private static int[][] arr;
    private static boolean[] visited;

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        visited = new boolean[N];

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

        // Combination
        comb(0, 0, 0);

        // Output
        System.out.println(ans);
    }

    private static boolean comb(int start, int cnt, int sum) {
        if (cnt == N / 2) {
            int temp = 0;
            for (int i = 0; i < N-1; i++) {
                for (int j = i+1; j < N; j++) {
                    if (!visited[i] && !visited[j])
                        temp += arr[i][j] + arr[j][i];
                }
            }

            ans = Math.min(ans, Math.abs(sum - temp));
            return ans == 0;
        }

        for (int i = start; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;

                int temp = 0;
                for (int j = 0; j < i; j++) {
                    if (visited[j])
                        temp += arr[i][j] + arr[j][i];
                }

                if(comb(i + 1, cnt + 1, sum + temp)) return true;

                visited[i] = false;
            }
        }
        return false;
    }
}

🔸 코드 해석 🔸

• 재귀 메서드 comb를 이용해 조합을 구현한다.
  • 팀원을 고를 때 마다 시너지 값을 누적해서 사용한다.
  • 팀원을 다 골랐으면 반대쪽 팀원들의 시너지 값 총합도 계산한다.
  • 시너지 값 차이를 ans에 업데이트한다.
• 모든 경우의 수를 확인하고 ans를 출력한다.

---

🔸 end 🔸

• 시간 초과가 떠서 계산값을 재귀 메서드에서 sum으로 들고다녔는데, 사실 하지 않아도 되고 다른 부분에서 구현 실수가 있었던 것 같다.