티스토리 뷰

생각

보호 필름을 생산했다! 이 보호 필름의 성능을 체크하려고 한다. 깊이가 D이고 넓이가 W인 보호 필름이 다음과 같이 주어졌을 때, 열 별로 같은 특성이 연속해서 가진 경우는 다음과 같다. 여기서 연속 조건 K 개를 만족해야, 성능 테스트를 통과하게 된다. 위의 보호 필름에서 다음과 같이 2 행에 약물을 투여할 경우 모든 열에서 K=3일 때 조건을 만족시킬 수 있다. 성능 테스트를 통과시키기 위해서 약물을 최소한으로 투입하는 횟수를 구하여라.


처음 생각

수학적인 공식이 전혀 떠오르지 않는다. 따라서 우선 완전 탐색을 진행하였다.

▶ 시간도 기존의 문제들 보다 긴 5초를 준다. 그만한 이유가 있어 주는 것이라 생각한다.

다음 생각

이걸 어떻게 완전 탐색으로 풀 수 있을까? 약물 주입이 변하는 조건이므로 해당 행 idx에 약물을 주입해 보는 경우와 주입해 보지 않는 경우로 진행을 하였다.
▶ 이 때, 약물이 A와 B로 나누어져 있으므로 두 개의 약물을 둘다 적용해서 DFS 탐색을 진행해 주어야한다.

▶ 진행시 재귀 메소드 solve()의 매개 변수로 행의 idx와 약물 투입 횟수 insert를 적용해주었다.

▶ 미포함시에는 원래 값으로 돌아와야하기 때문에 해당 행만 잠시 저장해두는 tArr[] 배열을 만들어 주어 관리하였다.


다다음 생각

DFS를 통해 모든 조건을 만들어서 완전 탐색을 진행하면 답은 당연히 도출해 낼 수 있을 것이다. 답도 중요하지만 메모리 사용량과 시간 경과도 중요하므로 재귀를 통해 DFS 탐색을 진행할 때는 가지치기가 핵심이된다.

이 문제에서 약물 투여 횟수가 이미 구한 min 값보다 클 경우 구할 필요없으므로 가지치기는 다음과 같이 해주었다.

1
if(insert>=min) return;
cs

▶ 가지치기를 하지 않고 check() 메소드를 호출 했을 경우

가지치기 결과1


▶ 가지치기를 하고 check() 메소드를 호출 했을 경우


가지치기 결과2



방안

1) 재귀를 통한 DFS시에는 항상 어떤 조건을 컷 해줄 수 있나를 고려해야 한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution {
    static int d,w,k;
    static int[][] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
        for(int i=1;i<=tc;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            d = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken()); // 합격 기준
            arr = new int[d][w];
            // 입력 받기
            for(int j=0;j<d;j++) {
                st = new StringTokenizer(br.readLine());
                for(int k=0;k<w;k++)
                    arr[j][k] = Integer.parseInt(st.nextToken());
            }
            min = Integer.MAX_VALUE;
            solve(0,0);
            sb.append("#"+i+" "+min+"\n");
        }
        System.out.print(sb);
    }
    
    // 두께 d는 3~13 , w는 1~20
    // 0은 A, 1은 B
    static int min;
    private static void solve(int idx,int insert) {
        // 최소 값을 찾는 것이므로 진행중 크거나 같은 값이 나오면 진행할 필요가 없다.
        if(insert>=min) return;
        
        // 조건이 다 만들어 졌다면 check하러 들어가기
        if(idx>=d) {
            // 통과 했다면 약물 개수 최소값 찾기
            if(check())
                min = Math.min(min, insert);
            return;
        }
        // 해당 idx 주입 안하기
        solve(idx+1,insert);
        
        // 원래 거 copy
        int[] tArr = new int[w];
        for(int i=0;i<w;i++)
            tArr[i] = arr[idx][i];
        
        // 해당 idx 주입 하기(A)
        for(int i=0;i<w;i++)
            arr[idx][i] = 0;
        solve(idx+1,insert+1);
        
        // 해당 idx 주입 하기(B)
        for(int i=0;i<w;i++)
            arr[idx][i] = 1;
        solve(idx+1,insert+1);
        
        // copy한것 되돌려놓기
        for(int i=0;i<w;i++)
            arr[idx][i] = tArr[i];
    }
    
    private static boolean check() {
        // k개 연속
        for(int i=0;i<w;i++) {
            boolean flag = false;
            int t = arr[0][i];
            int cnt=0;
            // 연속된게 K개 있는지 찾자.
            for(int j=0;j<d;j++) {
                if(t==arr[j][i]) cnt++;
                else{
                    cnt=1;
                    t=arr[j][i];
                }
                // k개가 된다면 해당 열은 더 진행 할 필요 x
                if(cnt==k) {
                    flag=true;
                    break;
                }
            }
            // 한 줄이라도 안되면 바로 false
            if(!flag) return false;
        }
        return true;
    }
}
cs

댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday