SWEA - 2112 ) 보호 필름

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

SW Expert Academy

---

보호필름에는 층이 존재하는데, 이층은 가로 W ,세로 D의 크기를 가진다.

 

 검사합격 기준 K가 주어질때, 0부터 W-1까지의 열에서 연속해 같은숫자가 K개 주어지면 그 열은 합격기준을 통과한다

 

초기에 통과기준을 넘지못하면, 약품을 투입해서 세로 D중 몇개를 한문자로 바꿀수 있다.

 

최소한의 약품을 사용하여 합격기준을 통과하고 싶을때, 최소한의 약품의 수를 구하는 문제이다.

 

문제는 간단하다. 최소한의 개수를 구하기위해서 D개중 1개 2개 3개...등 적절하게 뽑하서 약품을 넣어서 바꾸어

 

보고, 그상태의 배열이 합격기준을 통과하는지 ? 안하는지만 계산하면된다.

 

1. 입력 그대로 합격기준을 통과하는지?

 

2. 약품1개 D개중 1개를선택하는 서브셋을 구한다.

 

 3. 해당 Index의  row를 문자하나로 바꾼다.

 

4. 검사해본다.

 

5. 1개로 안되면 약품개수를 2개로 늘리고 D개중 2개를 선택하는 방법으로 해본다.

 

위의 방법을 반복하다 통과하면 그 통과약품개수를 리턴하면된다.

 

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Solution {
    static int answer =0;
    static int D,W,K;
    static int map[][];
    static int drug = 1;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(st.nextToken());
        for(int tc= 1; tc <= t; tc++) {
            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];
            int copy[][]= new int[D][W];
            for(int y= 0 ; y < D ; y++) {
                st= new StringTokenizer(br.readLine());
                for(int x= 0 ; x< W; x++) {
                    map[y][x] = Integer.parseInt(st.nextToken());
                }
            }
            int count[] = new int[D]; int cnt=0;
            if(check(map) != W){
                top:
                for(;drug <K;drug++) {
                    for(int i = 0 , size = (1<<D) ; i <size ; i++) {
                        cnt=0;
                        for(int j = 0 ; j < D ; j ++) {
                            if((i & ( 1<<j)) != 0) {count[j]=1; cnt++;}
                            else {count[j]=0; }
                        }
                        if(cnt == drug) {
                            for(int index = 0 ; index < D ;index++) {copy[index] = Arrays.copyOfRange(map[index], 0, W);}
                            for(int index = 0 ; index < D ; index++) {
                                // 0으로
                                if(count[index]==1) {
                                    for(int x = 0 ; x < W ; x++) {
                                        copy[index][x] =0;
                                    }
                                }
                            }
                            if(check(copy) == W) {
                                answer = drug;
                                break top;
                            }
                            for(int index = 0 ; index < D ;index++) {copy[index] = Arrays.copyOfRange(map[index], 0, W);}
                            for(int index = 0 ; index < D ; index++) {
                                // 1으로 
                                if(count[index]==1) {
                                    for(int x = 0 ; x < W ; x++) {
                                        copy[index][x] = 1;
                                    }
                                }
                            }
                            if(check(copy) == W) {
                                answer = drug;
                                break top;
                            }
                        }
                    }
                }
            }
            else {
                answer = 0;
            }
            
            if(drug == K) answer = K;
             if(K ==1) answer =0;
            sb.append("#"+tc+" "+answer+"\n");
            answer= 0; drug =1;
        }
            System.out.print(sb);
    }
    public static int check(int mapc[][]) {
        int cnt=0;
        for(int x = 0 ; x < W ; x++) {
            top :
            for(int y = 0 ; y < D ; y++) {
                // K개가 같은지 확인
                int t = mapc[y][x];
                if( y + K <=D) {
                    for(int z = y+1 ; z < y + K ; z++) {
                        if(t != mapc[z][x]) {
                            break;
                        }
                         
                        if(z == (y + K -1)) {
                            cnt++; break top;
                        }
                         
                    }
                }
            }
        }
        return cnt;
    }
 
}

 

---