[백준 JAVA] 14889 스타트와 링크, 합 이용

[문제링크] 스타트와 링크 실버2

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

14889번: 스타트와 링크

팀원이 되는경우 계산하는 부분을 두 가지로 나누어 코딩하였다.

 

[1번 풀이] vistied 되었다면 A팀으로 생각하여 백트랙킹후 이중포문으로 계산

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

public class Main {
    private static boolean visited[];
    private static int map[][];
    private static int min = Integer.MAX_VALUE;

    private static void solution(int n, int d,int start) {
        if (n == d) {
            int sum =0;
            for(int i=0;i<n*2;i++){
                for(int j=0;j<n*2;j++){
                    if(visited[i] && visited[j]) sum += map[i][j];
                    else if(!visited[i]&&!visited[j]) sum-=map[i][j];
                }
            }

            min = Math.min(min, Math.abs(sum));
        } else {
            for (int i = start ; i < n * 2; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    solution(n,d+1,i);
                    visited[i]=false;
                }
            }
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int num = Integer.parseInt(br.readLine());
        map = new int[num][num];
        visited = new boolean[num];
        for (int i = 0; i < num; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < num; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        solution(num / 2, 0,0);
        System.out.println(min);
    }
}

 

[2번 풀이] 이중포문으로 팀이 되는경우를 각 계산하지 않고 미리 각 행,열을 더해두고 

계산 부를 O(n)으로  처리하는 방법

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

public class Main {
    private static boolean visited[];
    private static int map[][];
    private static int all[];
    private static int min = Integer.MAX_VALUE;

    private static void solution(int n, int d,int start) {
        if (n == d) {
            int sum =0;
            for(int i=0;i<n*2;i++){
                if(visited[i])sum+= all[i];
                else sum -= all[i];
            }

            min = Math.min(min, Math.abs(sum/2));
        } else {
            for (int i = start ; i < n * 2; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    solution(n,d+1,i);
                    visited[i]=false;
                }
            }
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int num = Integer.parseInt(br.readLine());
        map = new int[num][num];
        visited = new boolean[num];
        all = new int[num];
        for (int i = 0; i < num; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < num; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                all[i]+= map[i][j];
                all[j]+= map[i][j];
            }
        }

        solution(num / 2, 0,0);
        System.out.println(min);
    }
}