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

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

14889번: 스타트와 링크

 

풀이 방법

사람 N/2 명을 스타트팀으로 뽑는 모든 조합에 대해 완전 탐색한다.

스타트팀 사람을 모두 뽑은 뒤엔 뽑히지 않은 나머지 사람을 링크팀으로 하여 두 팀의 S합의 차이를 구한다.

이때, 재귀 호출을 이용하여 조합을 구현하는 데 i번째를 뽑았을 경우에 대해 모두 탐색한 뒤엔 i번째를 뽑지 않는 경우로 돌아가야 하므로 스타트에 추가했던 것을 pop 하여 상태 복구를 한 후 (백트래킹) 다음 탐색을 진행한다.

 

코드

import java.io.*;
import java.util.*;

public class Main {

    static int N;
    static int answer = Integer.MAX_VALUE;
    static int[][] S;
    static Stack<Integer> start = new Stack<>();

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

        // S 입력 받기
        for(int i=0; i<N; i++) {
            String[] line = br.readLine().split(" ");
            for(int j=0; j<N; j++) {
                S[i][j] = Integer.parseInt(line[j]);
            }
        }
        pick(0);
        System.out.println(answer);
    }

    public static void pick(int index) {
        // N/2 개를 모두 뽑았으면
        if(start.size() == N/2) {
            List<Integer> link = new ArrayList<>();
            for(int i=0; i<N; i++) {
                if(!start.contains(i)) { // 스타트팀에 들어가지 않았다면
                    link.add(i); // 링크팀에 삽입
                }
            }
            answer = Math.min(answer, diff(start, link));
            return;
        }

        for(int i=index; i<N; i++) {
            // i번째 사람을 group1에 픽
            start.push(i);
            pick(i+1);
            start.pop(); // 다시 빼기
        }
    }

    //  두 그룹 차이 구하기
    public static int diff(List<Integer> start, List<Integer> link) {
        int sum1 = sum(start);
        int sum2 = sum(link);
        return Math.abs(sum1 - sum2); // 두 그룹 차이
    }

    // 그룹에서의 S 합 구하기
    public static int sum(List<Integer> group) {
        int sum = 0;
        for(int i=0; i<group.size(); i++) {
            int x = group.get(i);
            for(int j=0; j<group.size(); j++) {
                int y = group.get(j);
                sum += S[x][y];
            }
        }
        return sum;
    }
}