[백준] 15661번 - "링크와 스타트" (Java)

www.acmicpc.net/problem/15661

15661번: 링크와 스타트

---

난이도 : 실버1

 

백준의 스타트와 링크 문제와 많이 유사합니다. 차이점은 두 팀의 인원수가 딱 절반으로 나눠떨어지는 것이 아닌, 최소 1명 이상만 있으면 팀으로 간주하고 두 팀의 능력치 차이를 구하는 것입니다. 

 

해당 문제의 시간 제한은 2초입니다. 약 2억개의 데이터 안에서 풀 수 있습니다. 

문제의 조건에 따른 최악의 시간복잡도는 (4 ≤ N ≤ 20, N은 짝수)에서 한 데이터를 선택할 수있는 경우와 없는 경우 2가지로 N개를 원소를 가진 배열을 탐색하는 것이므로, 2^20 = 1,048,576. 

충분히 모든 경우를 탐색해도 풀 수 있는 문제입니다. 

 

하지만, 그에 맞게 풀이 코드 또한 2^N으로 구현하여야 합니다. 제가 작성한 첫 코드는 시간 초과가 났습니다. 테스트 케이스를 다 통과했는데 왜 시간 초과가 났는지 처음에는이해를 못했었습니다. 

시간 초과가 난 코드.

시간 초과가 난 이유를 모르고 있다가 백준님에게 직접 질문을 하여 얻은 답변을 올려드리겠습니다. (참고로 제가 직접 강의를 사고 올린 질문에 대한 백준님의 답변입니다.

참고로 코드 캡처한 부분 중, 주석 처리된 부분이 위 방식이고 for문이 아래 방식입니다. (47~48) -> (49~50)  , (49~50) -> (51~52)로 바꿔서 읽어주시길 바랍니다.

 

밑에 풀이는 위의 설명과 크게 관련은 없습니다. 위의 내용은 참고용으로만 봐주시길 바랍니다.

 

 

- void main()

모든 전역변수를 초기화 및 설정하고 nCr() 함수를 호출합니다. 그리고 정답인 min 변수를 출력합니다.

중요한 것은 nCr() 함수를 n-1만큼 호출합니다. 여기서 t가 n-1의 반복문 증가값이 되는데, t가 곧 팀원의 수 입니다. 문제 조건이 두 팀의 팀원 수는 정확히 절반으로 나누어 떨어지지 않는 것이므로, 가능한 모든 팀원의 수를 탐색합니다. 

 

- void nCr()

재귀 호출의 횟수를 t까지 하고 diff()함수를 호출해줍니다. t까지 한 이유는 위에서 설명했듯이 가능한 팀원의 수를 모두 탐색하기 위함입니다. 

 

- void recursion()

두 팀간의 능력치 최솟값을 구하는 함수입니다. 이 부분은 스타트와 링크 문제와 동일하게 구현하였습니다.

반복문의 범위에 대해 설명하자면 board의 i==j(대각선)을 기준으로 대칭을 이루기 때문에 board의 i == j (대각선)를 기준으로 위쪽만 탐색해주면 됩니다.  

  코드

public class BOJ_15661 {
	// BOJ / 15661번 / 링크와 스타트 / 조합, 백트래킹  / 실버1
	static int map[][], n, answer,t;
	static boolean v[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		v = new boolean[n];
		answer = Integer.MAX_VALUE;
		t=0;
		StringTokenizer stk;
		
		for(int i=0; i<n; i++) {
			stk = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<n; j++) {
				map[i][j] = Integer.parseInt(stk.nextToken());
			}
		}
		// t는 팀원 수. 팀원이 절반으로 떨어지는 것이 아니기 때문에 가능한 경우의 수를 모두 탐색한다.
		for(t=1; t<n; t++) {
			nCr(0,0);			
		}
		System.out.println(answer);
	}
	
	public static void nCr(int depth, int start) {
		
		if(depth == t ) {
			answer = Math.min(answer, diff());
			// 0이 나오면 가장 작은 최소값이기 때문에 더 이상 순회 할 필요가 없다. 
			// 시간을 조금 더 줄일 수 있다.
			if(answer == 0) {
				System.out.println(answer);
				System.exit(0);
			}
			return;
		}
		// i를 0이 아닌 start값으로 하면 시간 초과 방지및 시간을 크게 줄일 수 있다.
		for(int i=start; i<n; i++) {
			if(!v[i]) {
				v[i]= true;
				nCr(depth+1, i+1);
				v[i]=false;
			}
		}
	}
	
	public static int diff() {
		
		int start = 0; // v[] 값이 true면 start팀
		int link = 0; //  v[] 값이 false면 link팀
		for(int i=0; i<n-1; i++) {
			for(int j=i+1; j<n; j++) {
				if(v[i] && v[j]) {
					start += (map[i][j] +map[j][i]);
				}
				else if(!v[i] && !v[j]) {
					link += (map[i][j] + map[j][i]);
				}
			}
		}
		
		return  Math.abs(start - link);
	}
}

 

 

피드백은 얼마든지 환영합니다.