백준 14889번: 스타트와 링크
문제 설명
- N개의 숫자를 두 개의 그룹으로 나눌 수 있는 가능한 모든 경우의 수를 구하는 문제입니다.
접근법
- 조합을 통해 N개 중 N/2개를 뽑습니다.
- 한번 더 조합을 활용해 N/2개 중 2개를 뽑아 시너지를 계산합니다.
정답
import java.util.*;
public class Main {
static int N, T1, T2, answer;
static int[] our_team, total_memb;
static int[][] board;
public static void main(String[] args) {
// 입력값 세팅
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
board = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
board[i][j] = sc.nextInt();
}
}
answer = Integer.MAX_VALUE;
total_memb = new int[N];
our_team = new int[N / 2];
comb(0, 0);
System.out.println(answer);
}
public static void comb(int depth, int start) {
if (depth == N / 2) {
// 선택받지 못한 팀(enem_team) 배열을 구합니다.
List<Integer> total_memb = new ArrayList<Integer>();
for (int i = 0; i < N; i++) {
total_memb.add(i);
}
for (int i = 0; i < N / 2; i++) {
total_memb.remove(new Integer(our_team[i]));
}
int[] enem_team = new int[N / 2];
for (int i = 0; i < N / 2; i++) {
enem_team[i] = total_memb.get(i);
}
// 팀에서 2명씩 뽑아 두사람의 시너지를 전체 시너지(T1 혹은 T2)에 더합니다.
comb2(0, 0, our_team, new int[2], "T1");
comb2(0, 0, enem_team, new int[2], "T2");
// 전역변수로 선언했기 때문에 다른 조합에 사용하기 위해 0으로 초기화 합니다.
T1 = 0;
T2 = 0;
// 두 팀의 시너지 합의 차가 가장 적은 경우를 answer로 지정합니다.
answer = Math.min(answer, Math.abs(T1 - T2));
return;
}
for (int i = start; i < N; i++) {
our_team[depth] = i;
comb(depth + 1, i + 1);
}
}
public static void comb2(int depth, int start, int[] our_team, int[] pair, String team) { // 한 팀에서 2명을 뽑아 둘의 시너지를
// 계산합니다.
if (depth == 2) {
if (team.equals("T1")) {
T1 += board[our_team[pair[0]]][our_team[pair[1]]];
T1 += board[our_team[pair[1]]][our_team[pair[0]]];
} else {
T2 += board[our_team[pair[0]]][our_team[pair[1]]];
T2 += board[our_team[pair[1]]][our_team[pair[0]]];
}
return;
}
for (int i = start; i < our_team.length; i++) {
pair[depth] = i;
comb2(depth + 1, i + 1, our_team, pair, team);
}
}
}
기타
- 선택받지 못한 인원의 배열을 쉽게 구하는 법, 뽑은 숫자에서 2개를 추출하는 방법이 효율적이지 못한 것 같음
Author And Source
이 문제에 관하여(백준 14889번: 스타트와 링크), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qwerty1434/백준-14889번-스타트와-링크저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)