백준 14889 자바 스타트와 링크

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

14889번: 스타트와 링크

 

 

접근 아이디어

조합으로 풀었다. tgt배열에 true false값을 넣어서 조합의 절반만 순회하도록 하고 절반을 순회했다면 연산을 했다.

2중for문에 j = i+1을 하면서 대각선기준 아랫방향은 접근하지 않도록 하고 ij와 ji를 더해서 최솟값을 갱신하는 방식으로 풀었다.

 

잘 한 부분

조합을 생각한 것과 절반만 순회하는 아이디어를 잘 떠올렸다. 합칠 때도 양쪽을 한번에 구하는 방식을 어렵지 않게 구현했다.

 

부족한 부분

조합을 수행할 때 start+1을 재귀하는 것이 아니라 i+1을 재귀해야 하는데 이때문에 계속 시간초과가 났다. 또한 j = i+1도 잘 떠오르지 않았다.

 

 

 

package backjon;

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

public class 스타트와링크_14889 {

	static int N;
	static int[][] src;
	static boolean[] tgt;
	static int min;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		tgt = new boolean[N];
		src = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				src[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		min = Integer.MAX_VALUE;
		comb(0, 0);
		System.out.println(min);

	}

	private static void comb(int depth, int start) {
		if(depth == N/2) {
			sum();
			return;
		}
		
		for (int i = start; i < N; i++) {
			tgt[i] = true;
			comb(depth+1, i+1);
			tgt[i] = false;
		}
		
	}

	private static void sum() {
		int lsum = 0;
		int rsum = 0;
		for (int i = 0; i < N; i++) {
			for (int j = i+1; j < N; j++) {
				if(tgt[i] && tgt[j]) {
					lsum += src[i][j] + src[j][i];
				}
				else if(!tgt[i] && !tgt[j]) {
					rsum += src[i][j] + src[j][i];
				}
			}
		}
		
		min = Math.min(min, Math.abs(lsum - rsum));
	}
}