SWEA 2112. 보호 필름 :: 돼지개발자

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

"조합"

해당 문제는 어떤 row를 고를 것인지가 중요하다. 그리고 탐색한 결과를 모든 열이 k 개 연속된 숫자가 있는지 검사하는 것을 구현하는 것이 키포인트이다.

어떤 row를 고를 것인가는 조합과 같다. 

바꾸는 row의 개수를 최소로 하는 값을 찾으면 되므로, 아래의 경우를 탐색한다. 그리고 만족하는 값을 찾았다면 결과 출력.

모두 바꾸지 않는 것 ~모든 행을 다 바꾸는 것 

여기서 특정 row를 1 혹은 0 으로 바꾼 후에는 원래 상태로 복구 시켜주는 것이 필요하다. 마치 백트래킹 처럼.. 따라서 선택한 row를 0 혹은 1로 바꾸기전에 그 row 값을 temp 에 모두 복사시켜 놓고 탐색 종료 후 원상 복구 시켜준다~

.. 아래 풀이로 전체 테스트 케이스를 모든 값을 다 최대로 바꾸어 탐색을 많이 하게 해서 돌려보니 시간초과가 난다 ㅠ 하지만... SWEA에서는 통과했음. 뭔가 다른 로직이 필요한거 같기도하고... 아무튼.

집합 N 개에서 C개를 뽑는 조합의 기술(?) 과 열을 잘 체크하는 방법을 구현하면 쉽게 풀린문제.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
class Solution {
    
    static int T;
    static int d,w,k;
    static int map[][];
    static int min;
    static boolean find;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        T = Integer.parseInt(br.readLine());
        int t = 1;
        
        while(T-- > 0) {
            StringTokenizer 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];
            find = false;
            
            for (int i = 0; i < d; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < w; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            if(k == 1 || check()) {
                min = 0;
            }
            else {
                for (int i = 1; i <= k; i++) {
                    solve(-1,0,i);
                    if(find) break;
                }    
            }
            
            System.out.printf("#%d %d\n",t++,min);
        }
    }
    
    static void solve(int cur, int cnt, int K) {
        if(find) return;
        
        if(cnt == K ) {
            if(check()) {
                min = cnt;
                find = true;
            }
            return ;
        }
        
        for (int i = cur+1; i < d; i++) {
            int[] temp = copy(map[i]);
            
            for (int j = 0; j < 2; j++) {
                Arrays.fill(map[i],j);
                solve(i,cnt+1,K);
                if(find) return ;
            }
            map[i] = temp;
        }
    }
    
    static int[] copy(int[] arr) {
        int[] temp = new int[w];
        System.arraycopy(arr, 0, temp, 0, arr.length);
        return temp;
    }
    
    static boolean check() {
        for (int i = 0; i < w; i++) {
            boolean ok = false;
            for (int j = 0; j <= d-k; j++) {
                int temp = map[j][i];
                for (int z = 1; z < k; z++) {
                    temp += map[j+z][i];
                }
                if(temp == k || temp == 0) {
                    ok = true;
                    break;
                }
            }
            if(!ok) return false;
        }
        return true;
    }
 
}