SWEA 2112 보호 필름(JAVA) 📱

문제 링크

SW Expert Academy

문제 설명

약품 투입 횟수를 최소로 하여 성능검사를 통과할 수 있는 방법(합격기준 K)을 찾고, 이때의 약품 투입 횟수 출력

입력

첫 줄에 총 테스트 케이스의 개수 T가 주어진다.
두 번째 줄부터 T개의 테스트 케이스가 차례대로 주어진다.
각 테스트 케이스의 첫 줄에는 보호 필름의 두께 D, 가로크기 W, 합격기준 K가 차례로 주어진다.
그 다음 D줄에 보호 필름 단면의 정보가 주어진다. 각 줄에는 셀들의 특성 W개가 주어진다. (특성A는 0, 특성B는 1로 표시된다.)

출력

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.
각 줄은 “#x”로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)
출력해야 할 정답은 성능검사를 통과할 수 있는 약품의 최소 투입 횟수이다. 약품을 투입하지 않고도 성능검사를 통과하는 경우에는 0을 출력한다.

구조화

부분 집합 사용하여 약물 투입해서 조건에 부합한지 확인

부합하면 몇번의 약물 투입만으로 가능한지

약물 투입 횟수 최소값 갱신

소스 코드

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

public class Solution_2112_보호필름 {

	static int T, D, W, K, result;
	
	static int[][] map, copy;
	static boolean[] visited;
	static List<Integer> pick;
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		
		// testcase
		for (int t = 1; t <= T; t++) 
		{
			// input
			StringTokenizer 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];
			copy = new int[D][W];
			result = D;
			visited = new boolean[D];
			for (int i = 0; i < D; i++) 
			{
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < W; j++) 
				{
					int input = Integer.parseInt(st.nextToken());
					map[i][j] = input;
					copy[i][j] = input;
				}
			}
			// --- intput ---
			
			subSet(0,0);
			System.out.printf("#%d %d%n",t,result);
		}
	}

	private static void subSet(int cnt, int idx) {

		if(cnt>=result)
			return;
		// 기저 조건
		if(idx==D)
		{
			
			// 약물 투입해서 조건에 부합한지 확인
			// 부합하면 몇번의 약물 투입만으로 가능한지
			// 최소값 갱신
			// A(0), B(1)

			if(checkPass())
			{
				result = Math.min(result, cnt);
			}
			
			return;
		}
		
		subSet(cnt,idx+1);
		
		for (int i = 0; i < W; i++) 
		{
			copy[idx][i] =0;
		}
		subSet(cnt+1, idx+1);
		
		for (int i = 0; i < W; i++) 
		{
			copy[idx][i] =1;
		}
		subSet(cnt+1, idx+1);
		
		for (int i = 0; i < W; i++) 
		{
			copy[idx][i] = map[idx][i];
		}
	}

	private static boolean checkPass() {
		
		for (int j = 0; j < W; j++) 
		{
			int checkCnt = 1;
			int prev = copy[0][j];
			int max  = 0;
			for (int i = 1; i < D; i++) 
			{
				if(copy[i][j]==prev)
				{
					checkCnt++;
				}
				else
					checkCnt=1;
				prev = copy[i][j];
				max = Math.max(max, checkCnt);
			}
			if(max<K)
				return false;
		}

		return true;
	}

}