2112 : 보호 필름(JAVA)

PROBLEM

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

SW Expert Academy

LOGIC

1. 나올 수 있는 모든 경우의 부분집합을 구한다
   1. 약품 처리를 하는 경우
   2. 약품A를 처리하는 경우
   3. 약품B를 처리하는 경우
2. 완성된 부분집합마다 성능 검사를 한다

CODE

package SWEA2112;

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

public class Main {
	
	static int film[][];
	static int thickness,width,passLimit;
	static int answer = Integer.MAX_VALUE;

	public static void main(String[] args) throws NumberFormatException, IOException 
    	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 1; tc<=T; tc++)
		{
			st = new StringTokenizer(br.readLine());
			
			thickness = Integer.parseInt(st.nextToken());//보호 필름의 두께 D
			width = Integer.parseInt(st.nextToken());//가로 크기 W
			passLimit = Integer.parseInt(st.nextToken());//합격 기준 K
			answer = Integer.MAX_VALUE;
			
			film = new int[thickness][width];
			for(int i = 0; i<thickness; i++)
			{
				st = new StringTokenizer(br.readLine());
				for(int j = 0; j<width; j++)
				{
					film[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			subset(0,0);
			
			System.out.println("#"+tc+" "+answer);
			
		}

	}

	private static void subset(int cnt, int index) 
   	 {
		if(cnt>=answer)
		{
			return;
		}
		
		if(index == thickness)
		{
			if(check())//검사에 통과 했다면
			{
					answer = cnt;					
			}
			return;
		}
		
		int saveBefore[] = film[index].clone();
		
		subset(cnt, index+1);//약품 처리하지 않는 경우
		
		useChemical(index, 0);
		subset(cnt+1,index+1);//약품 A를 처리하는 경우
		
		useChemical(index, 1);
		subset(cnt+1,index+1);//약품 B를 처리하는 경우
		
		film[index] = saveBefore;//약품 처리 전으로 되돌리기
	}
	
	private static boolean check() 
    	{
		int count, type;
		boolean isEqual = false;
		
		for(int i = 0; i<width; i++)
		{
			count = 1;
			type = film[0][i];
			isEqual = false;
			
			for(int j = 1; j<thickness; j++)
			{
				if(type == film[j][i])
				{
					count++;
				}
				else
				{
					type = film[j][i];
					count = 1;
				}
				
				if(count == passLimit)
				{
					isEqual = true;
					break;
				}
			}
			
			if(!isEqual) return false;
			
		}
		
		return true;
	}

	private static void useChemical(int row, int chemical)
	{
		for(int i = 0; i<width; i++)
		{
			film[row][i] = chemical;
		}
	}

}