[SWEA-2112] 보호필름

이 문제는 SWEA 모의 SW 역량테스트 문제이다.

 

 

 

이 번에도 문제가 엄청 길다. 

근데 예시들이 들어져 있어서 그렇지, 읽어보면 문제 자체는 이해하기 쉬운편이다.

어떻게 계산을 해야하나... 고민을 하다가 이런 로직을 세웠다.

 

1) 부분집합을 이용해 어디를 바꿔볼 지 정하기 (powerset)

2) A혹은 B로 바꿔보기 (change)

3) 필름이 만들어졌는지 확인 (check) 

4) 원상복구 (back)

 

이 로직을 모든 부분집합에 대해서 실행해주면 된다.

다행히 시간초과가 나지 않고 잘 통과 됐다. :)

 

 

import java.util.Scanner;

public class Solution {
	static int D,W,K,ans;
	static int[][] map;
	static int[][] copy;
	static boolean[] check, ab; //몇 번째 줄 바꿀건지, 뭘로 바꿀 건지.
	static int[] selected;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1; tc<=T; tc++) {
			D = sc.nextInt(); //두께
			W = sc.nextInt(); //가로
			K = sc.nextInt(); //합격기준
			
			map = new int[D][W];
			copy = new int[D][W];
			ans = 100000;
			
			for(int i=0; i<D; i++) {
				for(int j=0; j<W; j++) {
					map[i][j] = sc.nextInt();
					copy[i][j] = map[i][j];
				}
			}
			
			
			check = new boolean[D];
			boolean flag = check();
			if(flag) { //안바꿔도 가능한 경우
				System.out.println("#"+tc+" "+0);
				continue;
			}else {
				powerset(0);
				System.out.println("#"+tc+" "+ans);
			}
		}
	}
	
	static void powerset(int cnt) {
		if(cnt == D) {
			selected = new int[D];
			int idx = 0;
			for(int i=0; i<D; i++) {
				if(check[i]){ //뽑힌 것 저장
					selected[idx++] = i;
				}
			}
			//이미 더 작게 성공 했으니 돌릴필요 X.
			if(idx-1 >= ans)
				return;
			
			//다 뽑았으면 뽑힌것 A혹은 B로 넣어보고 돌려보기
			ab = new boolean[idx];
			change(0,idx);
			return;
		}
		check[cnt] = true;
		powerset(cnt+1);
		check[cnt] = false;
		powerset(cnt+1);
	}
	
	//A나 B중 선택해서 돌려보기
	static void change(int cnt, int num){
		if(cnt == num) {
			for(int i=0; i<num; i++) {
				if(ab[i]) { //true면 0으로 바꾸기
					for(int j=0; j<W; j++) {
						map[selected[i]][j] = 0; 
					}
				}else { //false면 1로 바꾸기
					for(int j=0; j<W; j++) {
						map[selected[i]][j] = 1; 
					}
				}
			}
			
			//다 바꿨으면 체크
			boolean flag = check();
			if(flag && (num-1)<ans) {
				ans = num;
			}
			back();
			return;
		}
		
		ab[cnt] = true;
		change(cnt+1, num);
		ab[cnt] = false;
		change(cnt+1, num);
	}
	
	//합격 기준 테스트
	static boolean check() {
		boolean flag = true;
		
		for(int j=0; j<W; j++) {
			for(int i=0; i<D-K+1; i++) {
				flag = true;
				for(int k=i; k<i+K; k++) {
					if(map[i][j] != map[k][j]) {
						flag = false;
					}
					if(!flag)
						break;
				}
				if(flag) {
					break;
				}
			}
			if(!flag) {
				return false;
			}
		}
		return true;
	}
	
	static void back() {
		for(int i=0; i<D; i++) {
			for(int j=0; j<W; j++) {
				map[i][j] = copy[i][j];
			}
		}
	}
}