SWEA 2112 [보호 필름]

SW Expert Academy 보호 필름 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu&categoryId=AV5V1SYKAaUDFAWu&categoryType=CODE

//SWEA는 문제를 무단으로 복제하는 것을 금지하기에, 자세하게 설명하지 않습니다.

성능검사를 하기 위해 필요한, 최소한의 약품 투입 횟수를 구하는 문제입니다.

해결방법은 다음과 같습니다.

1. 각 투입횟수마다 나올 수 있는 경우를 저장.  

-> A : 0, B : 1로 둔 뒤, 투입 횟수가 1회 : A : [0], B : [1]

     투입 횟수가 2회 : AA : [0 , 0], AB : [0, 1] , BA : [1, 0], BB : [1, 1]...

이런식으로 이진수를 통해 저장

2. 나올 수 있는 투약방법마다 DFS를 통해 인덱스의 조합을 고른다. 

-> 1회 : (0) , (1), (2) , (3), (4), (5). ..

->2회 : (0, 1), (0, 2), (0, 3) ... ... (1, 2), (1, 3) .... ( 4, 5)

3. 인덱스를 고를 때 마다, 해당 인덱스에 해당 약품투약을 해준다.

import java.util.*;
public class Solution {
    public static int T, D, W, K;
    public static int[][] Map = new int[13][20];
    public static int[] arr = new int[13];        //이진수 저장 
    public static boolean is_end;
    public static int Result = 0;
    public static boolean is_pass() {
        for(int j = 0; j < W; j++) {
            boolean line = false;
            for(int i = 0; i <= D - K; i++) {
                int num = 1;
                for(int k = 1; k < K; k++)  {
                    if(Map[i + k][j] == Map[i][j])
                        num++;
                }
                if(num == K) {
                    line = true;
                    break;
                }
            }
            if(!line)
                return false;
        }
        is_end = true;
        return true;
    }
    public static void DFS(int size, int index, int capacity) {
        if(size == capacity) {
            if(is_pass()) {
                Result = capacity;
                return;
            }
        }
        for(int i = index; i < D; i++) {
            int[] temp = new int[W];
            for(int j = 0; j < W; j++) {
                temp[j] = Map[i][j];
                Map[i][j] = arr[size];
            }
            DFS(size + 1, i + 1, capacity);
            for(int j = 0; j < W; j++)
                Map[i][j] = temp[j];
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        for(int t= 1; t<= T; t++) {
            D = sc.nextInt();
            W = sc.nextInt();
            K = sc.nextInt();
            Result = 0;
            is_end = false;
            for(int i = 0; i < D; i++) {
                for(int j = 0; j < W; j++) {
                    Map[i][j] = sc.nextInt();
                }
            }
            for(int i = 0; i <= D; i++) {
                if(i == 0) {
                    is_pass();
                }
                else {
                    for(int j =0; j < (int)Math.pow(2, i); j++) {
                        int num = j;
                        for(int k = i-1; k >= 0; k--) {
                            arr[k] = num%2;
                            num /= 2;
                        }
                        DFS(0, 0, i);
                        if(is_end)
                            break;
                    }
                    if(is_end)break;
                }
                if(is_end)break;
            }
            System.out.println("#" + t + " " + Result);
        }
    }
}