[SWEA] 모의 SW 역량 테스트_ 보호 필름

문제 출처: SW Expert Academy

SW Expert Academy

: 보호 필름의 단면이 주어지고 성능검사를 통과시키는 최소 약품 투입 횟수를 찾아야 한다.

: 모든 경우를 다 탐색해 볼 수 있는 방법에 성능검사를 해보지 않아도 되는 경우들을 가지치기 해야한다.

: 먼저 부분집합으로 각 행 중에 어떤 행을 어떤 약품을 투입할 것인지를 결정한다.

: 결정이 모두 끝나면 성능검사를 시행하는데 만약 약품 투입횟수가 지금까지의 최소 약품 투입 횟수보다 클 경우는 시행하지 않는다.

: 성능 검사 도중에도 만약 하나의 열이라도 성능검사를 통과하지 못할 경우 바로 false를 반환하도록 해서 해당 경우를 넘길 수 있도록한다.

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

public class Solution {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int D, W, K;
	static int[][] map;
	public static void main(String[] args) throws NumberFormatException, IOException {
		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			
			st = new StringTokenizer(br.readLine());
			
			D = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			
			map = new int[D][W];
			isSelected = new int[D];
			for (int i = 0; i < D; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j = 0; j < W; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			min = Integer.MAX_VALUE;
			int[][] temp = new int[D][W];
			if(K != 1 ) powerset(0, 0, temp);				
			else min = 0;
			sb.append(String.format("#%d %d\n", tc, min));
			
		}
		System.out.println(sb);
	}
	static int[] isSelected;
	static int min = Integer.MAX_VALUE;
	private static void powerset(int cnt, int sum, int[][] temp) {
		if(sum > K) return;
		if(cnt== D) {
			int count = 0;
			for(int i = 0; i < D; i++) {
				if(isSelected[i] == -1)count++;
				
			}
			// 검사하기
			if(D-count < min && check(temp)) {
				min = Math.min(min, D-count);
			}
			return;
			
		}
		isSelected[cnt] = -1;
		temp[cnt] = Arrays.copyOf(map[cnt], W);
		powerset(cnt+1, sum, temp);

		isSelected[cnt] = 0;
		Arrays.fill(temp[cnt], 0);
		powerset(cnt+1, sum+1, temp);
		temp[cnt] = Arrays.copyOf(map[cnt], W);
	
		isSelected[cnt] = 1;
		Arrays.fill(temp[cnt], 1);
		powerset(cnt+1, sum+1, temp);
		temp[cnt] = Arrays.copyOf(map[cnt], W);
	}
	private static boolean check(int[][] map) {
		for(int i = 0; i < W; i++) {
			int cnt = 0;
			int max = 0;
			int prev = map[0][i];
			for(int j = 0; j < D; j++) {
				if(prev == map[j][i]) cnt++;
				else {
					max = Math.max(cnt, max);
					cnt = 1;
					prev = map[j][i];
				}
				if(cnt >= K || max >=K) continue;
			}
			max = Math.max(cnt, max);
			if(max < K) return false;
		}
		
		return true;
	}
}