14889번 - 스타트와 링크

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

14889번: 스타트와 링크

 

 

 

 

 

 

예전에 순열과 조합 문제를 열심히 풀 때 풀어봤던 문제이다. 

다시 풀었더니 예전만큰 안 풀린다...ㅎ

 

 

 

 

 

팀을 2개로 나눠야 하므로 조합을 사용하여 nCn/2를 하면 된다.

그리고 결과를 visited 배열에 저장하여 방문한 팀은 스타트팀, 않은 팀은 링크팀으로 나눠 점수를 계산해 주면 된다.

 

중간에 시간 초과가 났는데, 재귀부분에서 combination(i + 1, count + 1)여야 하는데, i대신 start로 했더니 틀렸다...

 

 

 

 

 

코드

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

public class Main {
	static int N;
	static int[][] arr;
	static boolean[] visited;
	static int min= Integer.MAX_VALUE;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		
		arr = new int[N + 1][N + 1];
		visited = new boolean[N + 1];
		
		for(int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
			for(int j = 1; j <= N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		//처리
		combination(1, 0); //조합 : nCn/2
		
		//출력
		System.out.println(min);
	}

	public static void combination(int start, int count) {
		if(count == N /2) {
			min = Math.min(min, difference());
			return;
		}
		
		for(int i = start; i < N + 1; i++) {
			if(visited[i] != true) {
				visited[i] = true;
				combination(i + 1, count + 1);
				visited[i] = false;
			}
		}
	}

	public static int difference() { //두 팀의 능력치 차이
		int sumStart = 0;
		int sumLink = 0;
		
		for(int i = 1; i < N + 1; i++) {
			for(int j = 1; j < N + 1; j++) {
				if(visited[i] && visited[j]) //스타트팀
					sumStart += arr[i][j];
				if(!visited[i] && !visited[j]) //링크팀
					sumLink += arr[i][j];
			}
		}
		
		return Math.abs(sumStart - sumLink);
	}

}

 

 

 

 

 

 

결과