SWEA2112_[모의 SW 역량테스트] 보호 필름

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

문제정리

1. 보호필름은 투명한 막을 D장 쌓아서 제작된다.

2. 막은 동일한 크기를 가진 바 모양의 셀들이 가로 방향으로 W개 붙여서 만들어진다.

3. 이렇게 제작된 필름은 두께 D, 가로 크기 W의 보호 필름이라고 한다. map[D][W]

4. 각 셀들은 특성 A 또는 특성 B를 가지고 있다. 보호 필름의 성능은 셀들의 특성이

어떻게 배치됨에 따라 결정된다.

5. 보호 필름의 성능을 검사하기 위해 합격기준 K라는 값을 사용한다.

6. 충격은 보호 필름 단면의 세로 방향으로 가해지므로, 세로 방향 셀들의 특성이 중요하다.

W방향에서 가해진다.

7. 단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만

성능검사를 통과하게 된다.

8. 성능검사에서 불통과한 열이 있다면 약품을 사용하여야 한다.

9. 약품은 막 별로(D) 투입할 수 있으면 이 경우 투입하는 막의 모든 셀들은 하나의 특성으로

변경된다.

10. 두께D, 가로크기 W인 보호 필름 단면의 정보와 합격기준 K가 주어졌을 때,

약품 투입 회수를 최소로 하여 성능검사를 통과할 수 있는 방법을 찾고,

이때의 약품 투입 횟수를 출력하라.

문제issue

1. 최대 3Pi13의 시간을 어떤식으로 줄여야 하나??

(1) 처음 중복순열 그대로 구현했을 때 테캐 27개 정도에서 시간초과

(2) min_result를 구했다면 다음 pi_arr에 2가 아닌 수가 min_result보다 크다면 marking 및 check를 해줄 필요 없음

47개에서 시간초과

(3) 중복순열을 만들 필요 없이 처음부터 check의 조건을 만족하는 경우 체크 49개에서 시간초과

(4) check에서 행에 해당하는 인덱스의 변화가 1씩 증가해서 최악의 경우 13!의 시간이 걸림

인덱스를 알파벳이 틀린 곳부터 다시 시작하게 만드니 pass....이사장 고마워....

해결흐름

1. map[D][W]로 만든다. map_clone[D][W]도 만든다.

A는 0 , B는 1이다.

2. alpa_arr = {2,0,1}을 만든다. 2는 바꾸지 않음 , 0은 A로 바꿈 , 1은 B로 바꿈

3. alpa_arr로 부터 pi_arr[D]에다가 중복순열을 만든다.

(1) map_clone에 map을 복사한다.

(2) 중복순열 한 개마다 행을 해당하는 알파벳으로 변경해주고

(3) W열을 검사해서 동일한 A 혹은 B가 K개 연속됨을 확인한다. 만약 한개의 열이라도 만족하지

못한다면 다음 열은 더이상 볼필요가 없다.

5. W열 검사

for W ~

   while D ~

      for check = D ; check < D + K ; check++

6. Pi() 중복순열을 만들어주는 메소드 , marking() 지정해준 행을 A혹은B로 map_clone을 변경해주는 메소드

check() 보호필름의 조건을 만족하는지 보는 메소드

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
 
    private static int D;
    private static int W;
    private static int K;
    private static int result;
    private static int min_result;
    private static int cnt;
    private static int[][] map;
    private static int[][] map_clone;
    private static int[] pi_arr;
    private static int[] alpa_arr = { 2, 0, 1 }; // 2는 안바꿔줌 , 0은 A로 바꿔줌 , 1은 B로 바꿔줌
 
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test_case = Integer.parseInt(br.readLine().trim());
        for (int tc = 1; tc <= test_case; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            D = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            map = new int[D][W];
            map_clone = new int[D][W];
            pi_arr = new int[D];
            for (int i = 0; i < D; i++) {
                st = new StringTokenizer(br.readLine().trim());
                for (int j = 0; j < W; j++) {
                    int number = Integer.parseInt(st.nextToken());
                    map[i][j] = number;
                    map_clone[i][j] = number;
                }
            }
            result = 0;
            min_result = Integer.MAX_VALUE;
            // 안바꿔도 만족하는 경우 체크
            if (!check()) {
                Pi(0);
                System.out.println("#" + tc + " " + min_result);
            } else {
                System.out.println("#" + tc + " " + 0);
            }
        } // end of tc
    } // end of main
 
    private static void Pi(int len) {
        if (len == D) {
            for (int i = 0; i < D; i++) {
                for (int j = 0; j < W; j++) {
                    map_clone[i][j] = map[i][j];
                }
            }
            // min_cnt보다 많이 바꿔야 한다면 볼필요 없음
            cnt = 0;
            for (int i = 0; i < D; i++) {
                if (pi_arr[i] != 2)
                    cnt++;
            }
            if (min_result < cnt)
                return;
            // 변경하는 행 변경하고
            marking();
            // 열을 검사
            if (check()) {
                result = 0;
                for (int i = 0; i < D; i++) {
                    if(pi_arr[i] != 2) result++;
                }
                if(min_result > result)
                    min_result = result;
            }
            return;
        }
        for (int i = 0; i < alpa_arr.length; i++) {
            pi_arr[len] = alpa_arr[i];
            Pi(len + 1);
        }
    } // end of Pi
 
    private static void marking() {
        // 변경해야 하는 행을 변경
        for (int i = 0; i < D; i++) {
            if (pi_arr[i] == 0) {
                for (int j = 0; j < W; j++) {
                    map_clone[i][j] = 0;
                }
            } else if (pi_arr[i] == 1) {
                for (int j = 0; j < W; j++) {
                    map_clone[i][j] = 1;
                }
            }
        }
    } // end of marking
    
    private static boolean check() {
        // W열 검사
        for (int i = 0; i < W; i++) {
            boolean w_flag = false;
            int idx = 0;
            while (idx <= D - K) {
                int d_cnt = 1;
                for (int check = idx + 1; check < idx + K; check++) {
                    if (map_clone[idx][i] == map_clone[check][i]) {
                        d_cnt++;
                    } else {
                        break;
                    }
                }
                if (d_cnt >= K) {
                    w_flag = true;
                    break;
                }
                idx += d_cnt;
                // 하나의 열이라도 만족 못하면 더 이상 볼필요 없음
            }
            if (!w_flag) {
                return false;
            }
        }
        return true;
    } // end of check
} // end of class