21.09.11 기록

백준 알고리즘 14889 풀이

🎆끄적여본 오답…

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

public class B14889 {
    public static int N;
    public static int[][] nums;
    public static boolean[] team;
    public 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());
        nums = new int[N][N];
        team = new boolean[N];

        StringTokenizer st;
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            for(int j = 0; j < N; j++) {
                nums[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0);
        System.out.println(min);
    }

    public static void dfs(int depth) {
        if(depth == (N/2)) {
//            min = Math.min(Math.abs(s1-s2), min);
            return;
        }

        for(int i = 0; i < N; i++) {
            if(!team[i]) {
                team[i] = true;
                // ...
            }
        }
    }
}

🎆해설(메모리 21.1MB, 시간 364ms로 통과)

-계속 연습하다 보면 언젠간 풀 수 있지 않을까 싶다..🙄

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

public class B14889 {
    public static int N;
    public static int[][] nums;
    public static boolean[] visit;
    public 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());

        nums = new int[N][N];
        visit = new boolean[N];

        StringTokenizer st;
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            for(int j = 0; j < N; j++) {
                nums[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0,0);
        System.out.println(min);
    }

    public static void dfs(int idx, int cnt) {
        if(cnt == N/2) {
            diff();
            return;
        }

        for(int i = idx; i < N; i++) {
            if(!visit[i]) {
                visit[i] = true;
                dfs(i+1, cnt+1);
                visit[i] = false;
            }
        }
    }

    public static void diff() {
        int teamStart = 0;
        int teamLink = 0;

        for(int i = 0; i < (N-1); i++) {
            for(int j = (i+1); j < N; j++) {
                if(visit[i] && visit[j]) {
                    teamStart += nums[i][j];
                    teamStart += nums[j][i];
                } else if (!visit[i] && !visit[j]) {
                    teamLink += nums[i][j];
                    teamLink += nums[j][i];
                }
            }
        }

        int val = Math.abs(teamStart - teamLink);

        //차이가 0이면 탐색 종료
        if(val == 0) {
            System.out.println(val);
            System.exit(0);
        }

        min = Math.min(val, min);
    }
}