[BJ]14889. 스타트와링크

BJ S3 14889 스타트와링크

이 문제는 SWExpert Academy의 모의_4012_요리사와 같은 문제입니다.

 

문제링크

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

14889번: 스타트와 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH

SW Expert Academy

 

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=JoW2hbaRy8I 

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

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

/**
 * @author 은서파
 * @since 2021. 11. 1.
 * @see https://www.acmicpc.net/problem/14889
 * @performance 기본 조합: 12320	288,조합 최적화: 12248	200, 능력치 구하기 최적화: 12176	112
 * @category #
 * @memo
 * SWEA_모의_4012_요리사와 동일한 문제
 */

public class BJ_S3_14889_스타트와링크{
	
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	
	static int N;
	static int [][] map;
	static int MIN;
	
	// map에 나온 모든 능력치의 합
	static int total;
	// 각 선수의 영향
	static int [] effectofN;
	
	public static void main(String[] args) throws IOException {
		input = new BufferedReader(new StringReader(src));
		N = Integer.parseInt(input.readLine());
		map = new int [N+1][N+1];
		for(int r=1; r<=N; r++) {
			tokens = new StringTokenizer(input.readLine());
			for(int c=1; c<=N; c++) {
				map[r][c] = Integer.parseInt(tokens.nextToken());
				total+=map[r][c];
			}
		}// 입력 완료
		
		MIN = Integer.MAX_VALUE;
		// N/2개를 뽑는 조
		// makeCombination(N/2, 1, new boolean[N+1]);
		
		// 전처리 - 각 선수의 영향 - 가로, 세로의 합
		effectofN = new int [N+1];
		
		for(int r=1; r<=N; r++) {
			int sum = 0;
			for(int c=1; c<=N; c++) {
				sum+=map[r][c] + map[c][r];
			}
			effectofN[r]=sum;
		}
		//System.out.println(Arrays.toString(effectofN));
		makeCombination2(N/2, 1, new boolean[N+1]);
		System.out.println(MIN);
	}
	
	private static void makeCombination2(int toChoose, int startIdx, boolean [] visited) {
		// 기저조건
		if(toChoose==0) {
			int temp = total;
			for(int i=1; i<=N; i++) {
				if(!visited[i]) {
					temp-=effectofN[i];
				}
			}
			MIN = Math.min(MIN,  Math.abs(temp));
			return;
		}
		// 재귀 상태
		// 실제 필요한 연산은 반틈이다.!
		for(int i=startIdx; i<=N -toChoose; i++) {
			visited[i]=true;
			makeCombination2(toChoose-1, i+1, visited);
			visited[i]=false;
		}
	}
	
	private static void makeCombination(int toChoose, int startIdx, boolean [] visited) {
		// 기저조건
		if(toChoose==0) {
			//System.out.println(Arrays.toString(visited));
			int sum = 0;
			for(int r=1; r<=N; r++) {
				for(int c=1; c<=N; c++) {
					// r==c 인 경우는 불필요 - 근데 어차피 0
					if(visited[r]==visited[c]) {
						if(visited[r]) {
							sum+=map[r][c];
						}else {
							sum-=map[r][c];
						}
					}
				}
			}
			MIN = Math.min(MIN,  Math.abs(sum));
			return;
		}
		// 재귀 상태
		// TTFF나 FFTT나 동일하기 때문에 전체를 다 구해볼 필요는 없다. 일종의 여집합
		for(int i=startIdx; i<=N -toChoose; i++) {
			visited[i]=true;
			makeCombination(toChoose-1, i+1, visited);
			visited[i]=false;
		}
	}
	// REMOVE_START
	private static String src = "6\r\n" + 
			"0 1 2 3 4 5\r\n" + 
			"1 0 2 3 4 5\r\n" + 
			"1 2 0 3 4 5\r\n" + 
			"1 2 3 0 4 5\r\n" + 
			"1 2 3 4 0 5\r\n" + 
			"1 2 3 4 5 0";
	// REMOVE_END
}