[백준] 14889: 스타트와 링크

비가츄·2022년 8월 11일

14889 Java 백준 조합

문제 설명

문제 링크는 여기.

14889번: 스타트와 링크

N명의 인원을 두 팀으로 분리한다. 이때 시너지 표를 참고하여 두 팀의 시너지 점수 차이의 최소 값을 구하면 된다.

각 팀의 시너지 점수 구하는 방법은 문제에 잘 나와있다.

접근

첫 번째로 해야하는 것은 팀 나누기이다. 이때 팀은 조합을 통해 쉽게 구할 수 있다.

한 팀당 인원은 N/2명인 것을 고려하여 조합 메서드는 아래와 같이 작성하였다.

public static int comp(int i, int idx, int N, int[][] S, boolean[] cnt) {
		// 팀을 다 정했으면 해당 팀인 경우 시너지 차이 반환
		if(idx==N/2) return compute(N, S, cnt);
		
		// 모든 경우 중 최소값 반환을 위해 초기 result은 Max값으로 설정
		int result = Integer.MAX_VALUE;

		// 조합이기 때문에 i는 인자로 받은 것을 그대로 반복문에 사용했음
		for(; i<N; i++) {
			cnt[i] = true;
			// 선택한 경우의 시너지 차이 값 받고 최소값을 선택해 저장
			result = Math.min(result, comp(i+1, idx+1, N, S, cnt));
			cnt[i] = false;
		}
		return result;
	}

이어서 팀이 결정된 이후의 시너지 연산 메서드는 다음과 같다.

private static int compute(int N, int[][] S, boolean[] cnt) {
		// 어쩌피 두 팀의 시너지 차이를 구하는 것이므로 temp에 더할 때 팀에 따라 부호를 달리하여
		// 처리하였음
		int result = 0;
		for(int r=0; r<N; r++) {
			int temp = 0;
			for(int c=0; c<N; c++) {
				if(cnt[r]==cnt[c]) temp+=S[r][c];
			}
			if(cnt[r]) result += temp;
			else result -= temp;
		}
		// 반환값이 음수일 수 있으므로 절댓값 씌움
		return Math.abs(result);
	}

소스코드

최종 제출 코드는 다음과 같다.

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		// 입력 처리부
		int N = Integer.parseInt(br.readLine());
		int[][] S = new int[N][N];
		boolean[] cnt = new boolean[N]; 
		
		for(int r=0; r<N; r++) {
			st = new StringTokenizer(br.readLine());
			for(int c=0; c<N; c++) {
				S[r][c] = Integer.parseInt(st.nextToken());
			}
		}

		// 실제 연산부
		System.out.println(comp(0, 0, N, S, cnt));
	}
	
	public static int comp(int i, int idx, int N, int[][] S, boolean[] cnt) {
		if(idx==N/2) return compute(N, S, cnt);
		int result = Integer.MAX_VALUE;
		for(; i<N; i++) {
			cnt[i] = true;
			result = Math.min(result, comp(i+1, idx+1, N, S, cnt));
			cnt[i] = false;
		}
		return result;
	}
	
	private static int compute(int N, int[][] S, boolean[] cnt) {
		int result = 0;
		for(int r=0; r<N; r++) {
			int temp = 0;
			for(int c=0; c<N; c++) {
				if(cnt[r]==cnt[c]) temp+=S[r][c];
			}
			if(cnt[r]) result += temp;
			else result -= temp;
		}
		return Math.abs(result);
	}
}