[SW Expert Academy] 2112. [모의 SW 역량테스트] 보호 필름

 

 

정답률 30퍼인데 의외로 잘 푼 것 같아서(시간도 다른 이들에 비해 짧고 메모리도 잘 써서)

 

공유해둔다.

 

재귀를 k 보다 더 깊이 들어가지 않음으로써 시간을 아낌.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    private static int min;
    private static int[] typeA;
    private static int[] typeB;
 
    public static void main(String[] args) throws Exception {
        FastScanner scan = new FastScanner();
        int testcases = scan.nextInt();
 
        for (int testcase = 1; testcase <= testcases; testcase++) {
            int height = scan.nextInt();
            int width = scan.nextInt();
            int k = scan.nextInt();
 
            int[][] film = new int[height][width];
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    film[i][j] = scan.nextInt();
                }
            }
 
            typeA = new int[width];
            typeB = new int[width];
            for (int i = 0; i < width; i++)
                typeB[i]++;
 
            min = k;
 
            func(film, height, width, k, 0, 0);
 
            System.out.println("#" + testcase + " " + min);
        }
    }
 
    private static void func(int[][] film, int height, int width, int k, int index, int count) {
        if (check(film, height, width, k)) {
            if (min > count)
                min = count;
            return;
        }
        if (count >= k - 1)
            return;
        for (int i = index; i < height; i++) {
            int[] temp = film[i];
            film[i] = typeA;
            func(film, height, width, k, i + 1, count + 1);
            film[i] = typeB;
            func(film, height, width, k, i + 1, count + 1);
            film[i] = temp;
        }
    }
 
    private static boolean check(int[][] film, int height, int width, int k) {
        for (int j = 0; j < width; j++) {
            int count = 1;
            for (int i = 0; i < height - 1 && count < k; i++) {
                if (film[i][j] == film[i + 1][j])
                    count++;
                else
                    count = 1;
            }
            if (count < k)
                return false;
        }
        return true;
    }
 
    private static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        private int nextInt() throws Exception {
            if (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
            return Integer.parseInt(st.nextToken());
        }
 
        private String nextString() throws Exception {
            return br.readLine();
        }
    }
}