SWEA- 보호필름 (JAVA)

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

SW Expert Academy

문제설명

다양한 푸는 방법이 존재한다. 조합을 이용하여 풀면 쉽게 풀 수 있다.

알고리즘

1. DFS를 이용하는데 종료조건은 투약횟수보다 cnt가 커지거나 세로길이를 넘어갈 때 이다.

2. 조건을 만족하면 최솟값을 구하고 return 한다.

3. 투여했을 때 안했을 때를 나눠서 조합으로 탐색한다.

구현

static int D; //두께  
static int W; //가로크기  
static int K; // 합격기준  
static int min;  
static int arr\[\]\[\];  
static int arr\_c\[\]\[\];  
static boolean check\[\];  
public static void main(String args\[\]) throws Exception  
{  
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));  
int T = Integer.parseInt(in.readLine().trim());  
for (int test\_case = 1; test\_case <= T; test\_case++)  
{  
StringTokenizer s = new StringTokenizer(in.readLine()," ");  
D = Integer.parseInt(s.nextToken());  
W = Integer.parseInt(s.nextToken());  
K = Integer.parseInt(s.nextToken());  
arr = new int\[D\]\[W\];  
arr\_c = new int\[D\]\[W\];  
check = new boolean \[D\];  
min=Integer.MAX\_VALUE;  
for (int i = 0; i < D; i++) {  
s = new StringTokenizer(in.readLine()," ");  
for (int j = 0; j < W; j++) {  
arr\[i\]\[j\] = Integer.parseInt(s.nextToken());  
arr\_c\[i\]\[j\] = arr\[i\]\[j\];  
}  
}  
DFS(0,0);  
System.out.println("#"+test\_case+" "+min);
    }//end TK
}
private static void DFS(int cnt,int idx) {
    if(cnt > min || cnt>D) //종료조건 D를 넘어가거나 cnt가 min보다 클때
        return;
    if(check_suc()) // 조건 만족하면
    {
        min =Math.min(min, cnt);
        return;
    }

    for (int i = idx; i < D; i++) {
        if(!check[i])
        {
            check[i] = true;
            inj(i,0,true); //0집어넣을때
            DFS(cnt+1,i);
            inj(i,0,false); //다시 0 빼고
            inj(i,1,true); //1집어넣음
            DFS(cnt+1,i);
            inj(i,1,false);//다시1뺴고
            check[i] = false;
        }
    }

}

private static void inj(int index, int val,boolean fl) {
    if(fl)
    {
        for (int i = 0; i < W; i++) 
            arr_c[index][i] = val;
    }
    else
    {
        for (int i = 0; i < W; i++) 
            arr_c[index][i] = arr[index][i];
    }
}
private static boolean check_suc() {
    int init_value= 0;
    for (int i = 0; i < W; i++) {
        int len_cnt = 1;
        for (int j = 0; j < D; j++) {
            if(j==0)
                init_value = arr_c[j][i];
            else
            {
                if(init_value != arr_c[j][i]) //값이 다르면 
                {
                    init_value = arr_c[j][i];
                    len_cnt = 1;
                }
                else
                    len_cnt++;
            }
            if(len_cnt ==K)
                break;
        }
        if(len_cnt != K)
            return false;
    }
    return true;
}