자바 - 백준 14889 / 스타트와 링크

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

14889번: 스타트와 링크

실버 2

 

구현 방법

처음에 보고 재귀로 풀어야 겠다는 생각이 들어서 바로 풀었지만 시간 초과가 났다. 생각해보니 문제는 조합을 의도한거였는데 순열로 풀어서 시간 초과가 난거였다. 구현 자체는 간단하다. 

1. n명의 사람들 중 반을 조합으로 선택한다.

2. 조합으로 선택된 사람들의 능력치를 구한다

3. 차이값을 계산하여 최소값인 경우 저장한다.

 

코드

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


/**
 * 백준 14889
 * 스타트와 링크
 * 실버2
 * https://www.acmicpc.net/problem/14889
 */
public class b14889 {
	
	//최소값
	static int min = Integer.MAX_VALUE;  
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		
		
		int[][] s = new int[n + 1][n + 1];
		for(int i = 1; i < n + 1; i++) {
			st = new StringTokenizer(br.readLine());
			
			for(int j = 1; j < n + 1; j++) {
				s[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		//스타트팀 true, 링크팀 false
		boolean[] visited = new boolean[n + 1];
		
		// 종료 조건, n/2 인 경우
		int cnt = 0;
		int cur = 1;
		
		selectP(s, n, visited, cnt, cur);
		
		System.out.println(min);
	}
	
	public static void selectP(int[][] s, int n, boolean[] visited, int cnt, int cur) {
		if(cnt == n/2) {
			int start = 0;
			int link = 0;
			
			for(int i = 1; i < n + 1; i++) {
				if(visited[i]) {
					for(int j = 1; j < n + 1; j++) {
						if(visited[j]) {
							start += s[i][j];
						}
					}
				} else {
					for(int j = 1; j < n + 1; j++) {
						if(!visited[j]) {
							link += s[i][j];
						}
					}		
			
				}
			}
			
			min = Math.min(min, Math.abs(start - link));
			return;
		}
		
		for(int i = cur; i < n + 1; i++) {
			if(!visited[i]) {
				visited[i] = true;
				selectP(s, n, visited, cnt + 1, i + 1);
				visited[i] = false;
			}
		}
		
		
		
	}
		
}

 

느낀 점

어떤 방식으로 풀어야 효과적일지 생각을 충분히 한뒤에 문제를 풀어야 한다는 점을 까먹지 말자!

 

참고 블로그

https://velog.io/@yul_00/AlgorithmJava-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9

[Algorithm/Java] 순열과 조합