모의 SW 역량테스트 (보호 필름)

[보호 필름 - 2112]

 

* 알고리즘

• 브루트포스

 

* 로직

• 각 행마다 주입할 수 있는 모든 경우의 수를 구한다
  • 약을 투여하지 않은 경우
  • A 약품을 투여한 경우
  • B 약품을 투여한 경우
• 구해진 각 경우의 수(조합)에 맞게끔 약품을 투여하고 검사를 진행한다
  • 각 열마다 같은 문자가 연속으로 k만큼 존재하면 다음 열로
  • 중간에 존재하지 않으면 false
• 검사에 통과하면 투여한 약품의 개수의 최솟값을 갱신한다
• 시간초과를 방지하기 위해 현재 가능한 약품의 값 < 투여한 약품의 개수 라면 return을 진행한다

 

//보호필름
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

	static int D, W; // 행,열
	static int K; // 합격 기준
	static int[][] map; // 0(A), 1(B)
	static int[] checked;
	static int answer;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int testCase = Integer.parseInt(br.readLine());
		int t = 1;
		while (t <= testCase) {
			String config = br.readLine();
			st = new StringTokenizer(config, " ");
			D = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());

			map = new int[D][W];
			for (int i = 0; i < D; ++i) {
				String input = br.readLine();
				st = new StringTokenizer(input, " ");
				for (int j = 0; j < W; ++j) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			answer = Integer.MAX_VALUE;
			checked = new int[D];
			int idx = 0;
			int medicine=0;
			
			doSolution(idx, medicine);

			System.out.println("#" + t + " " + answer);
			t++;
		}
	}

	private static void doSolution(int idx, int medicine) {
		if(answer < medicine) return;
		if(idx == D) {
			//해당 조합에 맞게 주입하고 체크하기
			if(doProcess()) {
				answer = Math.min(answer, medicine);
			}
			return;
		}
		
		checked[idx] = -1;
		doSolution(idx+1, medicine);	// 약품을 투여안하는 경우	
		
		checked[idx] = 0;
		doSolution(idx+1, medicine+1);	// A 약품을 투여하는 경우			
		
		checked[idx] = 1;
		doSolution(idx+1, medicine+1);	// B 약품을 투여하는 경우				
	}

	private static boolean doProcess() {
		int[][] tmp = new int[D][W];
		for(int i=0; i<D; ++i) {
			for(int j=0; j<W; ++j) {
				tmp[i][j] = map[i][j];
			}
		}

		//해당 조합에 맞게 주입
		for(int i=0; i<D; ++i) {
			if(checked[i] == 0) {
				injectMedicine(i, 0, tmp);										
			}
			else if(checked[i] == 1) {
				injectMedicine(i, 1, tmp);				
			}
		}		
		
		//테스트
		return checkFilm(tmp);
	}

	private static void injectMedicine(int row, int attribute, int[][] tmp) {			
		for(int j=0; j<W; ++j) {
			tmp[row][j] = attribute;
		}			
	}

	private static boolean checkFilm(int[][] tmp) {		
		for(int j=0; j<W; ++j) {			
			int cnt = 1;			
			for(int i=1; i<D; ++i) {
				if (tmp[i-1][j] == tmp[i][j]) cnt++;
				else cnt = 1;			
				
				if(cnt == K) break;
			}
            
			if(cnt < K) return false;		
		}

		return true;
	}
}