SW Expert Academy <보호 필름>

SW Expert Academy <보호 필름>

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

SW Expert Academy

---

보호 필름

W개의 셀로 이루어진 막 D개로 이루어진 보호필름이 있다. 즉, 두께가 D이고 가로 길이가 W인 보호필름이다.

보호필름이 충격을 받을 때는 보호필름 단면에 세로로 충격이 가해지기 때문에 보호필름의 성능검사는 각 단면의 세로 방향을 기준으로 진행된다. 성능검사를 통과하기 위해서는 단면의 모든 세로 방향에 대해 동일한 특성인 셀이 K개 이상 연속으로 존재해야 한다. (셀의 특성은 A, B 2가지 뿐이다.)

이때, 막을 기준으로 약품 처리를 통해 해당 막의 셀을 모두 동일한 특성으로 변경시킬 수 있다. 

보호필름에 대한 정보가 주어졌을 때, 성능 검사를 통과하기 위해 최소로 해야 하는 약품 처리의 횟수를 구하여라.

---

문제 해결

D가 최대 13, W가 최대 20이다.

문제를 읽어봤을 때, 각 막에 대해 변경 안함, A로 변경, B로 변경 3가지의 행동을 할 수 있다고 생각했고 이를 중복 순열로 구하면 3^13으로 약 160만으로 충분히 계산이 가능하다고 생각했다. (최소 횟수이기 때문에 가지치기도 많이 된다고 생각했다.) 그래서 중복 순열을 사용하여 문제를 풀이했다.

 

문제를 풀기 위해 만든 함수는 다음과 같다.

permutation(int cnt)

• D개의 막에 대해 할 행동을 재귀적으로 결정한다.
• 2면 변경하지 않고 1이면 B로 변경, 0이면 A로 변경한다.
• 만약 모든 막에 대한 결정이 끝났다면 check() 함수를 호출해 성능 검사를 진행한다.

check()

• 성능 검사를 진행하는 함수
• 변경해야 하는 막의 수를 count() 함수를 통해 알아내고 현재 저장된 최소 변경 횟수 (=Medicine) 보다 값이 크다면 함수를 종료한다.
• insert() 함수를 통해 결정된 막에 대한 행동을 진행해 새로운 보호 필름을 구한다.
• inspect() 함수를 통해 성능 검사를 진행한다.

inspect()

• 성능 검사를 진행하는 함수
• 모든 세로 방향에 대해서 K개 이상의 동일한 특성의 셀이 존재한다면 true를 반환하고 그렇지 않다면 false를 반환한다.

insert()

• 결정된 막에 대한 행동을 수행하여 새로운 보호 필름을 만들어 반환한다.

count()

• 결정된 막에 대한 행동 중 변화를 해야 하는 막의 개수를 구해 반환한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class SWEA_2112 {
    static int N, M, K, Medicine;
    static int[] select;
    static int[][] Film;
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            String[] inArr = br.readLine().split(" ");
            N = Integer.parseInt(inArr[0]);
            M = Integer.parseInt(inArr[1]);
            K = Integer.parseInt(inArr[2]);
            Film = new int[N][M];
            for (int i = 0; i < N; i++) {
                inArr = br.readLine().split(" ");
                for (int j = 0; j < M; j++) {
                    // 0이 A, 1이 B
                    Film[i][j] = Integer.parseInt(inArr[j]);
                }
            }   // end input
            if (K == 1){
                sb.append("#").append(t + 1).append(" ").append(0).append("\n");
                continue;
            }
            select = new int[N];
            Medicine = Integer.MAX_VALUE;
            permutation(0);
            sb.append("#").append(t + 1).append(" ").append(Medicine).append("\n");
        }
        System.out.println(sb);
    }

    static void permutation(int cnt) {
        if (cnt == N) {     // 모든 막에 대한 결정이 끝났다면
            check();
            return;
        }
        // 2면 변경 안함, 1이면 B로 변경, 0이면 A로 변경
        for (int i = 2; i >= 0; i--) {
            select[cnt] = i;
            permutation(cnt + 1);
        }
    }
    static void check() {
        // 변경해야 하는 막 수 알아내기
        int cnt = count();
        // 현재 정답보다 더 많이 변경해야 되면 볼 필요 없음
        if (Medicine <= cnt) return;
        // select에 따라 막에 약품 투입하기
        int[][] newFilm = insert();
        // 약품 투입한 보호필름에 대해 성능 검사하기
        // 성능 검사를 통과했다면 정답 업데이트
        if (inspect(newFilm)) {
            Medicine = cnt;
        }
    }

    static boolean inspect(int[][] newFilm) {
        for (int j = 0; j < M; j++) {
            int prev = newFilm[0][j];
            int cnt = 1;
            boolean flag = false;
            for (int i = 1; i < N; i++) {
                if (prev == newFilm[i][j]) {
                    cnt++;
                    if (cnt >= K) flag = true;
                } else {
                    prev = newFilm[i][j];
                    cnt = 1;
                }
            }
            if (!flag) return false;
        }
        return true;
    }
    static int[][] insert() {
        int[][] newFilm = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                newFilm[i][j] = Film[i][j];
            }
        }
        for (int i = 0; i < N; i++) {
            if (select[i] == 2) continue;
            for (int j = 0; j < M; j++) {
                newFilm[i][j] = select[i];
            }
        }
        return newFilm;
    }
    static int count() {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (select[i] == 2) continue;
            cnt++;
        }
        return cnt;
    }
}

---

결과

---