[SW Expert Academy] 보호필름

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

SW Expert Academy

public class 보호필름3 {
    static int answer;
    static int D, W, K;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            D = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            int film[][] = new int[D][W];
            for (int i = 0; i < D; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < W; j++) {
                    film[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            answer = Integer.MAX_VALUE;

            int originalFilm[][] = new int[D][];
            for (int i = 0; i < D; i++) {
                originalFilm[i] = film[i].clone();
            }

            dfs(0, 1, 0, film, originalFilm);
            dfs(0, 1, 1, film, originalFilm);
            dfs(0, 0, 2, film, originalFilm);
            System.out.println("#" + test_case + " " + answer);

        }
    }

    private static void dfs(int i, int cnt, int AB, int[][] film, int[][] originalFilm) {
        // answer보다 큰 cnt는 계산할 필요 없음
        if (answer <= cnt || i >= D) {
            return;
        }

        // 주입하고
        for (int j = 0; j < W; j++) {
            if (AB == 2) {
                film[i] = originalFilm[i].clone();
                break;
            }
            film[i][j] = AB;
        }
        // 체크하고
        if (filmCheck(film)) {
            answer = Math.min(answer, cnt);
        }

        dfs(i + 1, cnt + 1, 0, film, originalFilm);
        dfs(i + 1, cnt + 1, 1, film, originalFilm);
        // 2는 아무것도 안함
        dfs(i + 1, cnt + 0, 2, film, originalFilm);
    }

    private static boolean filmCheck(int[][] film) {
        for (int i = 0; i < W; i++) { // 가로
            int cnt = 1;
            int maxCnt = 1;
            for (int j = 0; j < D - 1; j++) { // 두께
                if (film[j][i] == film[j + 1][i]) {
                    cnt++;
                    maxCnt = Math.max(maxCnt, cnt);
                } else {
                    cnt = 1;
                }
            }
            if (maxCnt < K) { // 합격 기준에 못미치면
                return false;
            }
        }
        return true;
    }
}

소요시간 : 2시간
필름을 체크해서 합격기준에 못미치면 합격할때까지 약물 주입횟수를 늘리는 문제이다.
처음에는 조합을 이용해서 약물을 주입할 행을 선택하고 그 다음 A를 넣은 경우와 B를 넣은 경우를 완전탐색으로 해결하려 했습니다. 로직이 좀 복잡해서 틀린 부분을 찾기 힘들어서 다시 갈아엎고 재귀함수를 이용해서 첫째행부터 A를 주입한 값과, B를 주입한 값, 원래상태의 값 모두 완전탐색하여 최소 약물 주입 횟수를 구했습니다.