[SWEA] 4012. [모의 SW 역량테스트] 요리사

[SWEA] 4012. [모의 SW 역량테스트] 요리사 

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH&categoryId=AWIeUtVakTMDFAVH&categoryType=CODE&problemTitle=4012&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&&#none

SW Expert Academy

 

start 파라미터 가지고 combination 쓰는 것보다 부분집합 논리로 푸는게 더 쉬웠다.

1. 다만 주의할 점은 음식 번호는 1부터 시작하기 때문에 종료 조건을 줄 때 if(cnt>=N/2)가 아니라 if(cnt>N/2)라고 주어야 N/2번째의 경우에도 포함된다는 것

2. 그리고 모든 부분집합의 수를 탐색하는 것이 아니라 인자 개수가 N/2개인 부분집합만 봅는 것이기 때문에 if(L>N)라는 종료조건을 주지 않으면 안된다.

순열 / 조합 / 부분집합 코드 그 사이에 까먹었는지 헷갈렸다. 복습 많이 하자..

 

부분 집합 논리로 풀기

import java.io.*;
import java.util.*;
// 210314

public class Solution_모의_4012_요리사 {
	
	static int N, map[][], min;
	static ArrayList<Integer> A, B;
	static boolean[] visited;
	
	static int stoi(String str) {
		return Integer.parseInt(str);
	}
	
	// N C (N/2)
	static void subset(int cnt, int L) {
		
		if(cnt>N/2) {
			A = new ArrayList<>(); B = new ArrayList<>();
			for(int i=1; i<=N; i++) {
				if(visited[i]) A.add(i);
				else B.add(i);
			}

			min = Math.min(calPoints(), min);
			return;
		}
		
		if(L>N) {
			return;
		}
		
		visited[L] = true;
		subset(cnt+1, L+1);
		visited[L] = false;
		subset(cnt, L+1);
	}

	static int calPoints() {
		int pointA=0, pointB=0;
		
		for(int i=0; i<A.size(); i++) {
			for(int j=0; j<A.size(); j++) {
				pointA += map[A.get(i)][A.get(j)];
			}
		} 
		for(int i=0; i<B.size(); i++) {
			for(int j=0; j<B.size(); j++) {
				pointB += map[B.get(i)][B.get(j)];
			}
		} 
		
		return Math.abs(pointA-pointB);
	}
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("res/input_모의_4012_요리사.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = stoi(br.readLine().trim());
		
		for(int tc=1; tc<=T; tc++) {
			N = stoi(br.readLine().trim());
			
			map = new int[N+1][N+1]; // 음식은 1번부터 시작
			min = Integer.MAX_VALUE;
			visited = new boolean[N+1];
			
			for(int i=1; i<=N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for(int j=1; j<=N; j++) {
					map[i][j] = stoi(st.nextToken());
				}
			}
			
			subset(1, 1);
			sb.append("#" + tc + " " + min + "\n");
		}// tc
		
		System.out.println(sb.toString());
		br.close();
	}
}

 

start 파라미터로 combination

import java.io.*;
import java.util.*;

// 210219 

public class Solution_모의_4012_요리사 {
	static int N;
	static int[][] s;
	static int[] a, b;
	static int min;
	static boolean[] isSelected;
	
	static void combination(int cnt, int start) {
		if(cnt==N/2) {
			int ia=-1, ib=-1;
			for(int i=0; i<N; i++) {
				if(isSelected[i]) a[++ia]=i;
				else b[++ib]=i;
			}
			int sumA=cal(a), sumB=cal(b);
			min = Math.min(min, Math.abs(sumA-sumB));
			return;
		}
		
		for(int i=start; i<N; i++) {
			isSelected[i]=true;
			combination(cnt+1, i+1);
			isSelected[i]=false;
		}
	}
	
	static int cal(int[] arr) {
		int sum = 0;
		for(int k=0; k<arr.length; k++) {
			for(int z=k+1; z<arr.length; z++) {
				int i = arr[k], j =arr[z]; 
				sum += s[i][j];
				sum += s[j][i];
			}
		}
		return sum;
	}
	
	public static void main(String[] args) throws Exception {
		// System.setIn(new FileInputStream("res/input_모의_4012_요리사.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = stoi(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			
			N = stoi(br.readLine());
			s = new int[N][N]; // 음식 맛 시너지
			a = new int[N/2]; b = new int[N/2];
			min=Integer.MAX_VALUE;
			isSelected = 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] = stoi(st.nextToken());
				}
			}
			combination(0, 0);
			System.out.println("#" + tc + " " + min);
		}
		br.close();
	}//

	static int stoi(String str) {
		return Integer.parseInt(str);
	}

}