문제

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

코드 (Java)

import java.util.*;
import java.io.*;
 
class Solution
{
    private final static boolean A = false;
    private final static boolean B = true;
    private static boolean[][] film;
    private static boolean[] selected;
    private static boolean[] usedMed;
    private static int D, W, K;
     
    public static void main(String args[]) throws Exception
    {
//      System.setIn(new FileInputStream("res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T;
        T=Integer.parseInt(br.readLine().trim());
 
        for(int test_case = 1; test_case <= T; test_case++)
        {
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            D = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
             
            film = new boolean[D][W];
            selected = new boolean[D];
            usedMed = new boolean[D];
             
            for (int depth = 0; depth < D; ++depth) {
                st = new StringTokenizer(br.readLine().trim());
                for (int width = 0; width < W; ++width) {
                    if (Integer.parseInt(st.nextToken()) == 0) {
                        film[depth][width] = A; 
                    }
                    else {
                        film[depth][width] = B;
                    }
                }
            }
             
            int minCnt = D;
            for (int cnt = 0; cnt < D; ++cnt) {
                if (select(0, cnt)) {
                    minCnt = cnt;
                    break;
                }
            }
             
            bw.write("#" + test_case + " " + minCnt + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
     
    public static boolean select(int curD, int remainingCnt) {
        if (remainingCnt == 0) {
            //all selected, we solve.
            return solve();
        }
         
        if (D - curD < remainingCnt) {
            //impossible case. Even if we select all of'em, we still need to pick more.
            return false;
        }
         
        //case of selecting current Depth
        selected[curD] = true;
        usedMed[curD] = A; //A
        if (select(curD+1, remainingCnt-1)) {
            return true;
        }
        usedMed[curD] = B; //B
        if (select(curD+1, remainingCnt-1)) {
            return true;
        }
         
        //case of not selecting current Depth
        selected[curD] = false;
        if (select(curD+1, remainingCnt)) {
            return true;
        }
         
        return false;
    }
     
    public static boolean solve() {
        for (int width = 0; width < W; ++width) {
            int continuous = 1;
            int maxContinuous = -1;
            boolean prevVal = selected[0] ? usedMed[0] : film[0][width];
 
            for (int depth = 1; depth < D; ++depth) {
                boolean curVal = selected[depth] ? usedMed[depth] : film[depth][width];
                if (curVal != prevVal) {
                    maxContinuous = Math.max(maxContinuous,  continuous);
                    continuous = 1;
                    prevVal = curVal;
                } else {
                    continuous++;
                    if (continuous >= K) {
                        maxContinuous = K;
                        break;
                    }
                }
            }
             
            if (maxContinuous < K) return false;
        }
         
        return true;
    }
}

풀이

• 개인적으로 만족스러운(?) 풀이

• 결국 모든 경우의 수를 고려해야한다. 그런데 각 경우의 수에 맞게 직접 film을 저장한 자료구조를 바꾸기보단, 각 경우의 수를 추적하는 자료구조(해당 row에 약품 투여를 했는지, 했으면 뭘로 투여했는지)를 운용하는 것이 더 효율적이라고 생각해서 이를 만들고 풀었다. 그 생각 과정이 개인적으로 만족스러웠음.