백준 14889 스타트와 링크 (Java,자바)

이번에 풀어본 문제는
백준 14889번 스타트와 링크 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static int N;
    static int [][] map;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        StringTokenizer st;

        for(int i = 0; i < N; ++i)
        {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; ++j)
            {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int startPoint = (int)Math.pow(2,N/2)-1;
        StringBuilder sb;
        int tmp_cnt;
        for(int i = startPoint; i < 1 << N; ++i)
        {
            sb = new StringBuilder();
            tmp_cnt = 0;
            for(int j = 0; j < N; ++j)
            {
                if((i & (1 << j)) > 0)
                {
                    tmp_cnt++;
                    sb.append("1");
                }
                else
                {
                    tmp_cnt--;
                    sb.append("0");
                }
            }
            if(tmp_cnt == 0) diff(sb.toString());
        }
        System.out.print(min);
    }
    static void diff(String comb)
    {
        boolean [] team = new boolean[N];

        for(int i = 0; i < comb.length(); ++i)
        {
            if(comb.charAt(i) == '1') team[i] = true;
        }

        int total_s = 0;
        int total_l = 0;
        for(int i = 0; i < N; ++i)
        {
            for(int j = i+1; j < N; ++j)
            {
                if(team[i] && team[j]) total_s += map[i][j] + map[j][i];
                else if(!team[i] && !team[j]) total_l += map[i][j] + map[j][i];
            }
        }
        if(total_s == total_l)
        {
            System.out.print(0);
            System.exit(0);
        }
        min = Math.min(Math.abs(total_s - total_l),min);
    }
}

📝 풀이

두 팀을 나누어 각 팀의 능력치 차이가 가장 작을 경우의 수를 구하는 문제입니다. 우선 팀을 반으로 나누어주고, 생성된 조합으로 능력치 값을 누적하여 둘의 차이를 구해줍니다. 두 팀의 능력치가 같아질 경우 최솟값인 0을 구할 수 있으므로, 0을 출력한 후 프로그램을 종료해줄 수 있습니다.

📜 후기

비트마스킹도 잘 활용하고 싶어서 조금은 억지로 써봤는데, 아직 조금 헷갈리고 익숙하지 않은 것 같아요ㅠ 어렵지는 않았던 문제입니다!

좋은 웹페이지 즐겨찾기