[Baekjoon] 백준 14889 스타트와 링크 (D2 / 조합) - Java

링크

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

14889번: 스타트와 링크

 

 

 

 

문제 해석

- 문제 해석
N명의 사람을 두 팀으로 나눠야 함
주어지는 값은 i와j가 팀이 되었을 때 시너지를 나타냄
ij와 ji는 서로 다를 수 있음
두 팀의 능력치 차이가 최소가 되도록 만들기


- 입력
첫 번째 줄 : N  # 사람 수
나머지 줄 : 능력치


- 출력
두 팀의 능력치 정도가 최소가 되었을 때 차이

 

 

 

 

풀이 & 코드 해석

기본적인 완전탐색 문제입니다.

정해진 사람 수로 팀을 나눠야 하므로 조합을 이용하였습니다.

 

 

 

코드

import java.util.*;
import java.io.*;

public class 스타트와링크 {

	static int[][] map;

	static int team1[];
	static int N;
	static int answer;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		// 첫 번째 줄
		N = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		team1 = new int[N / 2];
		answer = Integer.MAX_VALUE;

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine()); // 나머지 줄
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		recursive(0, 0);

		System.out.println(answer);

	}

	private static void recursive(int cnt, int start) {
		// basis
		if (cnt == team1.length) {
//			System.out.println(Arrays.toString(team1));

			int[] team2 = new int[N / 2];
			int idx1 = 0;
			int idx2 = 0;
			for (int i = 0; i < N; i++) {
				if (idx1 <= (N / 2) - 1 && team1[idx1] == i) {
					idx1++;
				} else {
					team2[idx2] = i;
					idx2++;
				}
			}

			int teamPow1 = 0;
			for (int i = 0; i < team1.length - 1; i++) {
				for (int j = i; j < team1.length; j++) {
					teamPow1 += map[team1[i]][team1[j]];
					teamPow1 += map[team1[j]][team1[i]];
				}
			}

			int teamPow2 = 0;
			for (int i = 0; i < team2.length - 1; i++) {
				for (int j = i; j < team2.length; j++) {
					teamPow2 += map[team2[i]][team2[j]];
					teamPow2 += map[team2[j]][team2[i]];
				}
			}

			answer = Math.min(answer, Math.abs(teamPow1 - teamPow2));

			return;
		}

		// inductive
		for (int i = start; i < N; i++) {
			team1[cnt] = i;
			recursive(cnt + 1, i + 1);
			team1[cnt] = 0;
		}

	}
}

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java