백준 14889번

문제

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

14889번: 스타트와 링크

import java.util.Scanner;

public class Main14889 {

	public static int N;
	public static int person[];
	public static int ans[];
	public static boolean check[];
	public static int status[][];
	public static int[] start;
	public static int[] link;
	public static int result = 10;
	
	public static void compare(int cnt) {
		
		int sum = 0;
		int startSum = 0;
		int linkSum = 0;
		
		int k = 0;
		int l = 0;
		int m = 0;
		int n = 0;
		
		if (cnt == N/2) {
			
			for (int i=0; i<N/2; i++) {
				start[i] = ans[i];
				link[i] = ans[i+N/2];
			}
			
			for (int i=0; i<N/2; i++) {
				for (int j=0; j<N/2; j++) {
					k = start[i];
					l = start[j];
					m = link[i];
					n = link[j];
					
					startSum += status[k][l];
					linkSum += status[m][n];
				}
			}
			
			sum = Math.abs(startSum - linkSum);

			result = Math.min(result, sum);
			
		} else {
			
			for (int i=0; i<N; i++) {
				if (!check[i]) {
					ans[cnt] = person[i];
					check[i] = true;
					compare(cnt+1);
					check[i] = false;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		person = new int[N];
		ans = new int[N];
		check = new boolean[N];
		status = new int[N][N];
		start = new int[N/2];
		link = new int[N/2];
		
		for (int i=0; i<N; i++) {
			person[i] = i;
		}
				
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				status[i][j] = sc.nextInt();
			}
		}
		
		sc.close();
		compare(0);
		
		System.out.println(result);
	}
}

import java.util.Scanner;

public class Main14889 {

	public static int N;
	public static boolean check[];
	public static int status[][];
	public static int result = Integer.MAX_VALUE;
	
	public static void compare(int idx, int cnt) {
		
		int sum = 0;
		int startSum = 0;
		int linkSum = 0;

		if (cnt == N/2) {
			
			for (int i=0; i<N-1; i++) {
				for (int j=i+1; j<N; j++) {
					if (check[i] == true && check[j] == true) {
						startSum += status[i][j] + status[j][i];
					}
					else if (check[i] == false && check[j] == false) {
						linkSum += status[i][j] + status[j][i];
					}
				}
			}
			
			sum = Math.abs(startSum - linkSum);

			result = Math.min(result, sum);
			
		} else {
			
			for (int i=idx; i<N; i++) {
				if (!check[i]) {
					check[i] = true;
					compare(i+1, cnt+1);
					check[i] = false;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		check = new boolean[N];
		status = new int[N][N];
				
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				status[i][j] = sc.nextInt();
			}
		}
		
		sc.close();
		compare(0, 0);
		
		System.out.println(result);
	}
}

1. 첫번째는 시간초과로 실패. 두번째는 다른 글을 참고해서 수정해서 합격

 

2. 두 코드의 가장 큰 차이는 첫째, 첫번째 코드는 전체 경우의 수를 탐색했고 두번째 코드는 필요부분만 탐색한 것이다.

다시 말해 각 요소들을 바꿀 필요는 없기에 첫번째 코드처럼 짤 필요가 없다는 뜻이다. 어차피 true, false로 변경해주면서 팀만 바꿔주면 되기에 첫번째 코드는 불필요한 탐색을 하게된것이다.

 

3. 둘째, compare의 이중 for문에서 초기식과 조건식의 설정이다. 두번째 코드와 같은 식으로 설정할 경우 중복되는 값이 생기기에 출력이 달라진다.

 

4. https://st-lab.tistory.com/122

[백준] 14889번 : 스타트와 링크 - JAVA [자바]

참고했던 블로그인데 시간에서 다소 차이가 있다. 비슷한 방식이지만 결과가 0일 경우 바로 프로그램을 종료시켜서 시간을 더욱 단축 시킨듯 하다.

 

5. 간단한 응용문제임에도 많이 헤맸다. 완전히 이해되지는 않지만 비슷한 유형의 문제를 지속적으로 풀어 이해도를 반드시 높여야한다.