[알고리즘] 백준 - 스타트와 링크

메모리 초과 내 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class baekjoon_14889 {

    static int[][] arr;
    static int N;
    static int arrSum;
    static int ans = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        arr = new int[N+1][N+1];
        for (int i = 1; i <N+1; i++) {
            String[] inputs = br.readLine().split(" ");
            for (int j = 0; j < inputs.length; j++) {
                arr[i][j+1] = Integer.parseInt(inputs[j]);
            }
        }
        arrSum = 0;
        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < N + 1; j++) {
                arrSum += arr[i][j];
            }
        }
        solve(1, "", "");
        System.out.println(ans);
    }

    private static void solve(int curPerson, String startTeam, String linkTeam) {
        if (startTeam.length() == N/2 || linkTeam.length() == N/2) {
            if (linkTeam.length() == N/2) { // 만약 링크팀이 다 찼다면 나머지는 자동 스타트팀으로 채워준다.
                for (int i = curPerson; i <= N; i++) {
                    startTeam += Integer.toString(i);
                }
            } else if (startTeam.length() == N/2) {
                for (int i = curPerson; i <= N; i++) {
                    linkTeam += Integer.toString(i);
                }
            }

            int startSum = 0;
            int linkSum = 0;
            for (int i = 0; i < startTeam.length(); i++) {
                for (int j = 0; j < startTeam.length(); j++) {
                    startSum += arr[Character.getNumericValue(startTeam.charAt(i))][Character.getNumericValue(startTeam.charAt(j))];
                }
            }

            for (int i = 0; i < linkTeam.length(); i++) {
                for (int j = 0; j < linkTeam.length(); j++) {
                    linkSum += arr[Character.getNumericValue(linkTeam.charAt(i))][Character.getNumericValue(linkTeam.charAt(j))];
                }
            }
            ans = Math.min(ans, Math.abs(startSum - linkSum));
            return;
        }

        //curPerson이 스타트 팀에 들어가는 경우
        solve(curPerson + 1, startTeam + Integer.toString(curPerson), linkTeam);

        //curPerson이 링크 팀에 들어가는 경우
        solve(curPerson + 1, startTeam, linkTeam + Integer.toString(curPerson));
    }
}

핵심 로직은 결국 Combination을 구현하는 것 같은데 메모리 초과가 나서 통과하지 못했다.

통과한 다른 사람 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

//https://bcp0109.tistory.com/30

public class baekjoon_14889_2 {
    static int stoi(String s) { return Integer.parseInt(s); }

    static int n;
    static boolean[] visited;
    static int[][] arr;
    static int min = 987654321;

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

        n = stoi(br.readLine());
        visited = new boolean[n+1];
        arr = new int[n+1][n+1];

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

        comb(1, 0);
        System.out.println(min);
    }

    // 모든 팀의 조합 구하기
    static void comb(int start, int depth) {
        if(depth == n/2) {
            min = Math.min(min, getAbilityDifference());
            return;
        }

        for(int i=start; i<n+1; i++) {
            if(visited[i] != true) {
                visited[i] = true;
                comb(i+1, depth+1);
                visited[i] = false;
            }
        }
    }

    // 팀의 능력치 차이를 구하기
    static int getAbilityDifference() {
        int sumStart = 0;
        int sumLink = 0;

        for(int i=1; i<n+1; i++) {
            for(int j=1; j<n+1; j++) {
                // true 면 스타트팀
                if(visited[i] && visited[j])
                    sumStart += arr[i][j];

                // false 면 링크팀
                if(visited[i] != true && visited[j] != true)
                    sumLink += arr[i][j];
            }
        }

        return Math.abs(sumStart - sumLink);
    }
}

풀이 참고 블로그