<Algorithm> 156. 점심식사시간(SWExpert)

1. 점심식사시간(SWExpert)

   사용 알고리즘 :  비트마스크. 완전탐색

• 이거 푸는데 반나절이 걸린 것 같다... 오래 걸린이유가 문제를 잘못이해한데다가 테케가 46개나 통과됬다.

• 예외 사항 찾으려고 손수 최솟값을 구하려고 했는데 정답이 나오지가 않았다. 

• 그래서 예제를 다시해보니 계단이 꽉찾을때 앞사람이 이동 완료하는 시간 +1 아니라 동시에 출발이었다...

문제에 대한 접근&생각

1. 계단이 2개, 사람 최대 10명, n<=20 -> 완전탐색!
2. 어떤 사람이 어느 계단을 이용할지 판단 -> 비트마스크!
3. 한계단에 사람 3명초과 동시이용 불가 -> 결과조건

내 코드 

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 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140

import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner;   public class Solution {     static int n;     static List<Pair> plist;     static List<Pair> slist;     static int[] time = new int[2];     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int T = sc.nextInt();         for(int t = 1; t <= T; t++) {             /******************************              * 비트마스크를 통해 모든 경우에 대해              * 완전탐색한다. 이때 Queue를 이용해서              * 최대 3명이 될때 다음 들어오는 사람과              * 처음 사람을 비교해서 뒷사람의 내려오는               * 시간을 구한다.              *******************************/             n = sc.nextInt();             plist = new ArrayList<>();             slist = new ArrayList<>();             int cnt = 0;             for(int i = 0 ; i < n; i++) {                 for(int j = 0; j < n; j++) {                     int element = sc.nextInt();                     if(element == 1) {                         plist.add(new Pair(i, j));                     }else if(element > 1) {                         time[cnt++] = element;                         slist.add(new Pair(i, j));                     }                 }             }             res = Integer.MAX_VALUE;             solve();             System.out.println("#"+t+" "+res);         }     }          public static void solve() {                  for(int i = 0; i < 1<<plist.size(); i++) {                          step(i);         }     }          public static void step(int bit) {         //System.out.println(bit);         PriorityQueue<Integer> pq1= new PriorityQueue<>(Integer::compareTo);         PriorityQueue<Integer> pq2 = new PriorityQueue<>(Integer::compareTo);          Pair step1 = slist.get(0);          Pair step2 = slist.get(1);                   for(int i = 1,u=0; i < 1<<plist.size(); i= i<<1,u++) {             //System.out.println(u);             int d = 0;             Pair person = plist.get(u);             if((bit & i) == i) {                 d = Math.abs(step1.x-person.x)+Math.abs(step1.y - person.y);                 pq1.add(d+1);                 //System.out.println(step1.toString()+" "+person.toString()+" "+d);             }else {                 d = Math.abs(step2.x-person.x)+Math.abs(step2.y - person.y);                 pq2.add(d+1);                 //System.out.println(step2.toString()+" "+person.toString()+" "+d);             }         }         calc(pq1, pq2);     }     static int res;     public static void calc(PriorityQueue<Integer> pq1,PriorityQueue<Integer> pq2) {         Queue<Integer> queue1 = new LinkedList<>();         Queue<Integer> queue2 = new LinkedList<>();         if(!pq1.isEmpty())             queue1.add(pq1.poll());         if(!pq2.isEmpty())                 queue2.add(pq2.poll());                  while (!pq1.isEmpty()) {             if(queue1.size() == 3) {                 int t = queue1.poll();                 int wait = pq1.poll();                                  if((t+time[0])<wait) {                     queue1.add(wait);                 }else {                     queue1.add(t+time[0]);                 }             }else {                 queue1.add(pq1.poll());             }         }                  while (!pq2.isEmpty()) {             if(queue2.size() == 3) {                 int t = queue2.poll();                 int wait = pq2.poll();                 if((t+time[1])<wait) {                     queue2.add(wait);                 }else {                     queue2.add(t+time[1]);                 }             }else {                 queue2.add(pq2.poll());             }         }         int t1=0,t2=0;                  while(!queue1.isEmpty()) {             t1 = queue1.poll();         }                  while(!queue2.isEmpty()){             t2 = queue2.poll();         }         t1 += time[0];         t2 += time[1];         res = Math.min(res, Math.max(t1, t2));     }          static class Pair{                  @Override         public String toString() {             return "Pair [x=" + x + ", y=" + y + "]";         }         int x,y;         public Pair(int x, int y) {             this.x = x;             this.y = y;         }     } }   Colored by Color Scripter

cs

 

얻은 것

• 테케가 거의 다 통과해도 로직이 틀린 것 일 수도 있다. 

참고 & 출처