티스토리 뷰
생각
보호 필름을 생산했다! 이 보호 필름의 성능을 체크하려고 한다. 깊이가 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() 메소드를 호출 했을 경우
▶ 가지치기를 하고 check() 메소드를 호출 했을 경우
방안
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 |
'알고리즘 > SW Expert' 카테고리의 다른 글
[SW Expert] 1545. 거꾸로 출력해 보아요 (0) | 2018.10.14 |
---|---|
[SW Expert] 2117. [모의 SW 역량테스트] 홈 방범 서비스 (0) | 2018.10.13 |
[SW Expert] 2115. [모의 SW 역량테스트] 벌꿀채취 (0) | 2018.10.11 |
[SW Expert] 2105. [모의 SW 역량테스트] 디저트 카페 (0) | 2018.10.10 |
[SW Expert] 2477. [모의 SW 역량테스트] 차량 정비소 (0) | 2018.10.10 |
- Total
- Today
- Yesterday