<java> 백준 14889 - 완전탐색, DFS

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

 

간단한 문제이기는 하지만 완전 탐색이라고 마음먹지 않고
풀면 한없이 꼬이기 쉬운 문제 같았다.

 

<후기>

나는 항상 완전 탐색을 우선적으로 생각하지 않고

반복하지 않으면서 문제를 풀 수 있는 방식을 찾으려고 하여

많은 시간을 낭비하곤 한다.

항상 완전탐색을 우선적으로 생각하여 시간 복잡도를 계산한 후에

다른 방식을 탐색해야 겠다

 

문제 과정 자체는 어려울게 없었다.

그냥 각 n/2를 뽑은 후 A,.B로 나눈다음

각 점수를 더해서 합을 빼면 되는 문제이다.

 

이 과정에서 dfs를 잘 해서 팀을 잘 만들 수 있는가에 대한 문제이다.

귀찮음을 생각하지 않고 외울 수 있는 것은 외우자라는 마음을 먹었는데

이번에도 외우지 못해서 상당히 버벅거려 살짝 스스로 실망하였다.

 

static void dfs(int n, int k, int start){
    if(k == 0){
        // answer 재정립
        answer = Math.min(getTeamsGap(), answer);
        return;
    }

    for(int i = start; i< n; i++){
        v[i] = true;
        dfs(k - 1, i + 1);
        v[i] = false;
    }
}

  n개 중 k개 뽑기 -- 이제 좀 외우자! 

 

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

public class Q14889A {
    static int n, answer;
    static int[][] map;
    static boolean[] v;

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

        v = new boolean[n];
        map = new int[n][n];
        answer = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            StringTokenizer st = new StringTokenizer(reader.readLine());
            for(int j = 0; j < n; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(n/2 , 0);
        System.out.println(answer);
    }
    //중복되지 않게 n/2씩 뽑기
    static void dfs(int k, int start){
        if(k == 0){
            // answer 재정립
            answer = Math.min(getTeamsGap(), answer);
            return;
        }

        for(int i = start; i< n; i++){
            v[i] = true;
            dfs(k - 1, i + 1);
            v[i] = false;
        }
    }


    //map[i][j] 의 합구해서 차 return 하기
    static int getTeamsGap(){
        int a = 0;
        int b = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(v[i] && v[j]){
                    a += map[i][j];
                    continue;
                }
                if(!v[i] && !v[j]){
                    b += map[i][j];
                }
            }
        }
        return Math.abs(a-b);
    }
}

\\