[백준/BOJ] 14889 스타트와 링크 - JAVA - 실버1

[백준/BOJ] 14889 스타트와 링크 - JAVA - 실버1

문제

https://www.acmicpc.net/problem/14889

문제 분석

조건

• 짝수인 N명을 2팀으로 나누고, 각 팀의 시너지 차이를 최소화하는 문제이다.

풀이방법

• 비트마스킹을 사용하여 팀을 나누어주었다.
• 시작 조합은 각 팀에 N/2명만큼 있어야하므로 조합의 시작 부분을`1 << (N / 2) - 1`로 하고, 가장 앞 부호가 1이 되는 순간 기존과 팀원이 중복되기때문에 마지막 팀원은 2팀으로 고정되게 설정하였다.
  • `for (int i = 1 << (N / 2) - 1; i < 1 << (N - 1); i++)`
•  조합을 구하고 팀원수가 맞는다면 각 팀의 시너지를 구해주었다.

+

• 마지막 팀원을 고정하고 첫 부분도 고정은 했지만 비트마스킹 특성상 어쩔수없이 `1 << (N / 2) - 1` 부터 ` i < 1 << (N - 1)`까지 모든 수를 탐색하게 된다.

코드

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

public class Main {
    static int[][] board;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        int answer = Integer.MAX_VALUE;
        List<Integer> team1;
        List<Integer> team2;

        for (int i = 1 << (N / 2) - 1; i < 1 << (N - 1); i++) {
            team1 = new ArrayList<>();
            team2 = new ArrayList<>();
            for (int j = 0; j < N; j++) {
                if (((1 << j) & i) > 0) {
                    team1.add(j + 1);
                } else {
                    team2.add(j + 1);
                }
            }
            if (team1.size() != N / 2) {
                continue;
            }
            answer = Math.min(answer, Math.abs(getSynergy(team1) - getSynergy(team2)));
        }
        System.out.println(answer);
    }

    private static int getSynergy(List<Integer> team) {
        int count = 0;
        for (int member1 : team) {
            for (int member2 : team) {
                if (member1 == member2) {
                    continue;
                }
                count += board[member1][member2];
            }
        }
        return count;
    }
}

결과

++

2년 전 풀었던 문제를 스터디를 하며 다시 풀게 되었다. 그때는 재귀로 풀었는데 요즘은 조합 문제만 보면 비트마스킹을 이용해서 문제를 풀고싶어진다.

비트마스킹으로 구현은 더 쉽게 했지만 시간복잡도에서 모든 경우의 수를 탐색하느라 손해를 봤다. 또한 리스트를 반복적으로 초기화하면서 메모리면에서도 손해를 봤다. 정답을 맞았긴했지만 다음에는 정확한 경우의 수가 정해진다면 `Next Combination`을 사용해서 풀어야겠다.