SWEA[2112] - 보호필름

링크

SWEA[2112]

문제설명

• 완전탐색

문제풀이

• 완전탐색 + 가지치기 = 백트래킹
• 시간초과 신경써야함

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution2112 {

    public static int Ans=0;
    public static int D;
    public static int W;
    public static int K;
    public static int[][] map;
    public static int[][] n_map;

    public static void backup(int r) {
        for (int j = 0; j < W; j++) {
            n_map[r][j] = map[r][j];
        }
    }

    public static void put(int r, int color) {
        for (int i = 0; i < W; i++) {
            n_map[r][i]=color;
        }
    }

//    재귀탐색
    public static void Search(int cnt, int putn) {
//        답이 이미 나온 경우 && 현재 경우가 최대 경우를 넘어가면(min값 구해야 하므로)(가지치기)
        if(Ans>0 && Ans<=putn) {
            return;
        }
//        답을 찾은 경우
        if(chkpossible()) {
            Ans = putn;
            return;
        }
//        마지막 까지 다 탐색했는데 답이 안나온 경우
        if(cnt==D) {
            return;
        }

        for (int i = 0; i < 3; i++) {
            switch (i) {
            case 0:
//            투입안하거나
                Search(cnt+1,putn);
                break;
            case 1:
//            A투입하거나
                put(cnt,0);
                Search(cnt+1,putn+1);
                backup(cnt);
                break;
            case 2:
//            B투입하거나
                put(cnt,1);
                Search(cnt+1,putn+1);
                backup(cnt);
                break;
            }
        }
    }

    public static boolean chkpossible() {
        for (int i = 0; i < W; i++) {
            if (!chkrow(i)) {
                return false;
            }
        }
        return true;
    }

    public static boolean chkrow(int c) {
        int max = 0;
        int cnt = 1;
        int now = n_map[0][c];
        for (int i = 1; i < D; i++) {
            if(now==n_map[i][c]) {
                cnt++;
            }
            else {
                now=n_map[i][c];
                max = Math.max(max, cnt);
                if(max>=K) {
                    return true;
                }
                cnt=1;
            }
        }
        max = Math.max(max, cnt);
        if(max>=K) {
            return true;
        }
        return false;
    }



    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/swea/2112.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T=Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
//            입력
            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];
            n_map = new int[D][W];

//            {0:A, 1:B}
            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());
                    n_map[i][j] = map[i][j];
                }
            }

            Search(0,0);

            System.out.println("#"+test_case+" "+Ans);
            /*
             * 초기화
             */
            Ans=0;
        }//end test_case
    }//end main
}//end class

아쉬운점

• chkrow 할 때 마지막까지 안바뀌는 경우는 탈출체크 못했음
• 조합으로 풀었을 때
  • DCK 까지 경우의 수(K<=D)임 DCD까지 하려안해도 됨
    • sigma (2->N){DCN*2^N}만큼 경우의 수 나옴
  • 시간초과 고려를 못했음
• backup이 맵 전체를 백업하는게아니라 한줄만 백업해도 됨.
• 백트래킹 실수
  • 답 한번 찾으면 그걸로 끝냈었음.
    • 답을 한번 찾았다고 그게 최적의 답이 아닐 수 있음. 그래서 계속 탐색하면서 이미 나온 답보다 더 큰 가지는 쳐내야 함.
    • 답이 이미 나온 경우 && 현재 경우가 최대 경우를 넘어가면(min값 구해야 하므로)(가지치기)

시간 초과에 대한 고찰

조합으로 접근하였을경우 - {Depth 중 K미만 선택}*{A,B}^K 만큼의 경우의 수

public class nCrCount {

    public static int ncr(int n, int r) {
        int ans=1;
        for (int i = 0; i < r; i++) {
            ans*=(n-i);
        }
        for (int i = 0; i < r; i++) {
            ans/=(1+i);
        }
        return ans;
    }

    public static void main(String[] args) {
        int ans=0;
        for (int i = 2; i < 13; i++) {
            ans+=ncr(13,i)*Math.pow(2, i);
        }
        System.out.println(ans);
    }
}

O(N) = [필름 수정 하는 경우의 수]*[필름수정]*[필름 통과 체크](DC1 + DC2 + ... + DCK) * (D) * (W * D) = 1330104 * 260 = 4.4 * 10^9

시간초과 걸릴만함.

조합으로 할 경우 1개만 바꾸는 경우가 2개 바꾸는 경우에 포함되는데 그 결과를 재사용하지 못함. 그래서 탐색을 좀 더 많이 함.

완전탐색으로 접근하였을 경우 - {X,A,B}^Depth

O(N) = [필름 수정하는 경우의 수]^[Depth]^[필름 통과 체크] = 3^D*(W*D) = 3^13*20*13 = 4*10^8

애매함.

백트래킹 해줘야 시간초과 안남.

잘한점

• ispossible, put, backup 메서드 생성해서 간단하게 만듦
• n_map 생성
• 조합으로 짰다가 DFS로 새로짬.