swea: 4012 요리사

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

SW Expert Academy

1. nums배열 생성=>1,2,3,4,5,6,....N으로 조합만듬=>배열인덱스로 사용

2. result배열 생성=>크기가nCr의 r, ex)1,2,3에서 2개뽑으면 1,2 / 1,3 /2,3 이 됨.

3. comb(시작인덱스, 카운트=>r이되면 끝내려고)

if(cnt==r) {계산, 리턴}

for(i= 시작인덱스~N)

{

result[cnt]=nums[i]  => 조합생성

comb(i+1,cnt+1) => 다음함수는 내가쓴 i는 안쓰도록

}

 

4.계산

1~N까지 리스트B에 숫자넣음

resultA에 있는거 지움 => ex)A가 1,2,3 재료이면 B는 남은재료 4,5,6이 자동임

 

A:: resultA에서  2개씩 선택해서 합구하기   

//{1,2,3}이면 1고정,2 / 1고정,3 /2고정,3 ->(1,2)(1,3)(2,3)나옴

이걸map의 인덱스로 사용

B:: resultB에서 2개씩 선택해서 합구하기

 

답=최소값(기존답,AB차이)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Solution_4012_유동훈 {

	static int answer=Integer.MAX_VALUE;
	static int N;
	static int[][] map;
	static int[] result;
	static int r;
	//static boolean[] check;
	static List<Integer> nums;
	
	static void calc()
	{
		//result에 없는 나머지 = B의 음식 조합
		//int[] resultB=new int[N/2];
		List<Integer> resultB=new LinkedList<>();
		for(int i=1;i<=N;++i)
		{
			resultB.add(i);
		}
		for(int i=0;i<N/2;++i)
		{
			resultB.remove((Integer)result[i]);
		}
		
		int A=0;
		int B=0;
		
		
		for(int i=0;i<N/2 -1;++i)
		{
			for(int j=i+1;j<N/2;++j)
			{
				A=A+map[result[i]-1][result[j]-1];
				A=A+map[result[j]-1][result[i]-1];
			}
			
		}
		for(int i=0;i<N/2 -1;++i)
		{
			for(int j=i+1;j<N/2;++j)
			{
				B=B+map[resultB.get(i)-1][resultB.get(j)-1];
				B=B+map[resultB.get(j)-1][resultB.get(i)-1];
			}
			
		}
		
		answer=Math.min(answer, Math.abs(A-B));
		
		
		
	}
	static void print()
	{
		
	}
	static void comb(int idx, int cnt)
	{
		r=result.length;
		if(cnt==r)
		{
			calc();
			return;
		}
		
		for(int i=idx;i<N;++i)
		{
			//check[i]=true;
			result[cnt]=nums.get(i);
			comb(i+1,cnt+1);
			//check[i]=false;
		}
		
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        //st = new StringTokenizer(br.readLine());
        
        int T = Integer.parseInt(br.readLine());
        for(int test_case=1;test_case<=T;++test_case)
        {
        	N=Integer.parseInt(br.readLine());
        	map = new int[N][N+1];
        	
        	for(int i=0;i<N;++i)
        	{
        		st = new StringTokenizer(br.readLine());
        		for(int j=0;j<N;++j)
            	{
            		map[i][j]=Integer.parseInt(st.nextToken());
            	}
        	}
        	
        	
        	nums=new LinkedList<>();
    		for(int i=1;i<=N;++i)
    		{
    			nums.add(i);
    		}
        	//check=new boolean[N+1];
        	result=new int[N/2];
        	comb(0,0);
        	
        	
        	
        	
        	
        	
        	System.out.println("#"+test_case+" "+answer);
        	answer=Integer.MAX_VALUE;
        }

	}

}