[Dev-Ping9] 백준 14889번 - 스타트와 링크 (Java)

 

[1차 시도]

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 메모리가 터져나간다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

공부를 좀 더해야겠다....😢

 

[2차 시도]

 

 

 

# 문제설명

 일단 문제 설명에 따라 nCn/2 의 경우를 탐색해야한다.

 탐색한 후, 각 경우에서 또 (n/2)! 만큼 탐색하면 되는 것 같다.

 

 그러나 나는 A팀에 1번이 포함됬을 경우,  [1][] , [][1] 을 모두 지워버리는 식으로

 A팀에 포함된 모두를 아래와 같이 지워버리고 B팀의 점수를 집계했다.

 

 그 결과 2308ms -> 1212ms 라는 좋지 않은 수행시간 점수를 받아버렸다...  

 

 

 

 

# 구현코드

 

1차 코드 (메모리 303,956KB / 시간 2308ms)

 - nCr 마구잡이로 짜보고, 2차원배열도 clone()을 통해 복사가 되는지 확인해보았다. (된다...!!!)

 - 통과한게 신기할정도로 처참한 성능

 - nCr 코드 같은건 어느정도 정형화 할 필요가 있음을 깨달았다. (그래도 nCr 은 나쁘지않게 짠 것 같다.)

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main{
    static int[][] stat;
    static boolean[] visited;
    static int optimal=Integer.MAX_VALUE;

    static void makeZero(int [][] arr, int idx){
        for(int i=1; i<arr.length; i++){
            arr[idx][i]=0;
            arr[i][idx]=0;
        }
    }

    static int getSum(int [][] arr){
        int sum=0;
        for(int i=1;i<arr.length;i++){
            for(int j=1;j<arr.length;j++){
                sum+=arr[i][j];
            }
        }
        return sum;
    }

    static int cal(int size){
        int a=0, b=0;
        int[][] aTeam = new int[size+1][size+1];
        int[][] bTeam = new int[size+1][size+1];
        
        for(int i=0; i<stat.length; i++){
            aTeam[i]= stat[i].clone();
            bTeam[i]= stat[i].clone();
        }


        for(int i=1; i<=size; i++){
            for(int j=1;j<=size; j++){
                if(visited[i]){ //a팀
                    makeZero(aTeam, i);
                }else{
                    makeZero(bTeam, i);
                }
            }
        }
        

        a = getSum(aTeam);
        b = getSum(bTeam);

        return Math.abs(a-b);
    }
    static void printArr(int n){
        for(int i=1; i<=n; i++){
            System.out.print(visited[i]+ " ");
        }
        System.out.println();
    }

    static void nCr(int start,int n,int r,int end){
        
        if(end == n/2){
            optimal = Math.min(cal(n),optimal);
            return;
        }
        if(start == n+1) return;
            
        visited[start]=true; //a Team
        nCr(start+1, n, r, end+1);
        visited[start]=false;
        nCr(start+1, n, r, end);
        
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        stat = new int[n+1][n+1];
        visited = new boolean[n+1];
        //init array
        for(int i =1; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            for(int j=1; j<=n; j++){
                stat[i][j] = Integer.parseInt(st.nextToken());
            }
        }


        nCr(1, n, n/2, 0);
        System.out.println(optimal);
        
    }
}

 

 

2차 코드 (메모리 38,568KB / 시간 1212ms) - 메모리는 9할가량, 시간은 5할가량 줄였다..!

 - 탐색결과를 boolean 으로 나타내지않고, 숫자형태로 가져온다면 매핑시간이 줄어들 것에 착안 

 - for문의 시행횟수를 줄여보았다. (그래도 아직 부족한 것 같다. 3차 시도에는 접근 방식을 바꾸어야겠다.)

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main{
    static int[][] stat;
    static int cnt;
    static int optimal=Integer.MAX_VALUE;
    static List<Integer> aTeamList;
    static List<Integer> bTeamList;


    static boolean isContain(int i, List<Integer> list){
        for(int k=0;k<list.size();k++){
            if(i==list.get(k)){
                return true;
            }
        }
        return false;
    }

    static int cal(int size){
        int a=0, b=0;

        //b 팀 합산
        for(int i=1; i<=size; i++){
            if(isContain(i,aTeamList)) continue;
            for(int j=1;j<=size; j++){
                if(isContain(j,aTeamList)) continue;
                else if(i==j) continue;
                b+=stat[i][j];
            }
        }
        
        // a 팀 합산
        for(int i=1; i<=size; i++){
            if(isContain(i,bTeamList)) continue;
            for(int j=1;j<=size; j++){
                if(isContain(j,bTeamList)) continue;
                else if(i==j) continue;
                a+=stat[i][j];
            }
        }

        return Math.abs(a-b);
    }

    static void nCr(int start,int n,int r,int end){
        
        if(end == n/2 && bTeamList.size()==n/2){
            
            optimal = Math.min(cal(n),optimal);
            return;
        }
        if(start == n+1) return;

            
        aTeamList.add(start); //aTeam
        nCr(start+1, n, r, end+1);
        aTeamList.remove((Integer)start);
        bTeamList.add(start);
        nCr(start+1, n, r, end);
        bTeamList.remove((Integer)start);
        
            
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        stat = new int[n+1][n+1];
        //init array
        for(int i =1; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            for(int j=1; j<=n; j++){
                stat[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        aTeamList= new ArrayList<>();
        bTeamList= new ArrayList<>();

        nCr(1, n, n/2, 0);
        System.out.println(optimal);
    }
}