[Java] BOJ14889, 백준 - 스타트와 링크

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

14889번: 스타트와 링크

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	43663	22239	12921	47.774%

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

 

i | j	1	2	3	4
1		1	2	3
2	4		5	6
3	7	1		2
4	3	4	5

 

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

 

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

 

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

 

<풀이>

점수를 저장할 배열: int[][] score

어느 팀에 들어갈지 체크하는 배열: boolean[] arr

 

재귀를 이용하여 풀것이기 때문에 종료조건과 반복조건을 생각한다.

종료조건 1: 한 팀의 인원수를 전부 선택했을 경우 > 결과 비교 후 종료

종료조건 2: 인덱스가 N을 초과한 경우 > 그냥 종료

 

반복조건 1: 해당 인원을 팀에 선택하지 않았을 경우 > 그냥 넘어간다 ( start를 1 더해줌 )

반복조건 2: 해당 인원을 팀에 선택한 경우 > 배열에 표시하고 넘어간다 ( start를 1 더하고 arr배열의 값을 true로 변경 )

 

종료했을 때는 arr을 이용하여 어느 팀인지 판단하고,

score를 이용하여 점수를 계산하여 최솟값과 비교한다.

 

시간복잡도

각각의 사람을 1번팀, 2번팀에 넣어보며 조건을 만족했을 때의 값을 찾는것이기 때문에

N명이 각자 들어갈 수 있는 팀 : 2개

시간복잡도는 2^N이 된다.

N의 범위가 20까지기 때문에 N=20으로 계산해보면 백만정도

시간 제한이 2초기 때문에 충분

 

1차 코드

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

public class Main {
	private static int n;
	private static boolean[] arr;
	private static int min;
	private static int[][] score;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		score = new int[n][n];
		// 팀 선택을 위한 배열 arr
		arr = new boolean[n];

		// 입력부
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				score[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		min = 4000;
		go(0, 0);
		System.out.println(min);

	}

	// 1팀에 선택된 인원수를 cnt하고, arr배열을 이용해 체크해준다.
	private static void go(int cnt, int start) {
		if (cnt >= n / 2) { // 종료 조건: 1팀의 네 명 모두 선택 완료
			int sum1 = 0;
			int sum2 = 0;
			for (int i = 0; i < n; i++) {
				for (int j = i + 1; j < n; j++) {
					if (arr[i] && arr[j]) {
						sum1 += score[i][j] + score[j][i];
					} else if (!arr[i] && !arr[j]) {
						sum2 += score[i][j] + score[j][i];
					}
				}
			}
			min = Math.min(min, Math.abs(sum1 - sum2));
			return;
		}

		// 종료조건2: 인덱스가 넘어가는 경우
		if (start >= n)
			return;

		// 선택 안하는 경우
		go(cnt, start + 1);

		// 선택 하는 경우
		arr[start] = true;
		go(cnt + 1, start + 1);
		arr[start] = false;
	}
}

 

2차 코드

의미 없는 반복을 없애주기 위해서 종료 조건을 추가해주었다.

   > 이걸 백트래킹이라고 함

• min값이 0이 된 경우 ( 더 연산해줘도 0보다 작아질 수 없음 )
• 남은 사람 + 팀에 이미 선택된 사람 < N/2인 경우 ( 남은 사람들을 다 더해도 문제의 조건을 채울 수 없음)

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

public class Main {
	private static int n;
	private static boolean[] arr;
	private static int min;
	private static int[][] score;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		score = new int[n][n];
		// 팀 선택을 위한 배열 arr
		arr = new boolean[n];

		// 입력부
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				score[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		min = 4000;
		go(0, 0);
		System.out.println(min);

	}

	// 1팀에 선택된 인원수를 cnt하고, arr배열을 이용해 체크해준다.
	private static void go(int cnt, int start) {
		if (cnt >= n / 2) { // 종료 조건: 1팀의 네 명 모두 선택 완료
			int sum1 = 0;
			int sum2 = 0;
			for (int i = 0; i < n; i++) {
				for (int j = i + 1; j < n; j++) {
					if (arr[i] && arr[j]) {
						sum1 += score[i][j] + score[j][i];
					} else if (!arr[i] && !arr[j]) {
						sum2 += score[i][j] + score[j][i];
					}
				}
			}
			min = Math.min(min, Math.abs(sum1 - sum2));
			return;
		}

		// 종료조건2: 인덱스가 넘어가는 경우
		// 종료조건3: min이 0인경우
		// 종료조건4: 남은 인원(n-start) + 팀에 선택된 인원(cnt) < n/2인경우
		if (start >= n || min == 0 || n - start + cnt < n / 2)
			return;

		// 선택 안하는 경우
		go(cnt, start + 1);

		// 선택 하는 경우
		arr[start] = true;
		go(cnt + 1, start + 1);
		arr[start] = false;
	}
}

 

16ms나 줄였당(사실 얼마안됨)