백준 - 항구

문제 설명

모든 화물을 크레인을 통해 옮기려고 한다.

크레인으로 모든 화물을 옮기는데 걸리는 최소 시간을 구하는 문제이다.,

각 크레인은 최대로 화물을 올릴 수 있는 크기가 정해져 있다.

제한 범위

크레인의 총 개수 50

화물의 개수 10,000

가장 큰 화물을 들 수 있는 크레인이 가장 큰 적재화물을 드는 식이 최선이라고 생각했다.

크레인을 내림차순

적재 화물을 내림차순

주의사항

적재화물을 처음에 우선순위 큐로 소비하는 식으로 구현했다.

하지만 반례케이스가 존재했다.

크레인 = [10,8,1]

적재화물 = [10,8,7,1,1] -<우선순위 큐>

단 2번 만에 옮김 수 있는 경우인데 적재화물 머리(7) 일 때, 다음 화물 1에서 크레인 1을 사용하여 옮길 수 있어 10,8,1을 걸리는데 1분이 걸리고 그다음 7,1,1을 옮겨 2분 안에 완료할 수 있다.

우선순위 큐는 계속 머리로 비교하여 시간을 넘겼을 경우 7부분에서 막혀 크레인들이 못 드는 것으로 인식하고 넘어가기 때문이다.

풀이

static Scanner sc=new Scanner(System.in);
    static StringTokenizer st;
	public static void main (String[] args) throws java.lang.Exception {
	    st=token();
	    int n = parse(next());
	    List<Integer> crane=new ArrayList<>();
	    
	    st=token();
	    for(int i=0; i<n; i++){
	        crane.add(parse(next()));
	    }
	    
	    st=token();
	    int m = parse(next());
	    List<Integer> box=new ArrayList<>();
	    // 우선순위큐로 소비하면 뒤에 크레인을 사용하여 옮김수 있음에도 불구하고 못옴긴다.
	    // 최대한 가용가능한 크레인으로 다 옴기는 것이 최선이다.
	    st=token();
	    for(int i=0; i<m; i++){
	        box.add(parse(next()));
	    }
	    
	    Collections.sort(box,Collections.reverseOrder());
	    Collections.sort(crane,Collections.reverseOrder());
	    if(crane.get(0)<box.get(0)){ // 크레인이 못들면 영원히 못옮김
	        print(String.valueOf(-1));
	        return;
	    }
	    
	    int answer=0;
	    while(box.size()!=0){
	        int boxIdx=0;
	        for(int j=0; j<n; j++){
	            if(!box.isEmpty() && box.get(boxIdx)<=crane.get(j)){
	                box.remove(boxIdx);
	            }else{
	                boxIdx++;
	                j--;
	            }
	            if(boxIdx>=box.size()){
	                break;
	            }
	            if(box.size()==0) break;
	        }
	        
	        answer++;
	    }
	    
	    print(String.valueOf(answer));
	}
	
	static void print(String s){
	    System.out.println(s);
	}
	
	static StringTokenizer token(){
	    return new StringTokenizer(sc.nextLine());
	}
	
	static String next(){
	    return st.nextToken();
	}
	
	static int parse(String s){
	    return Integer.parseInt(s);
	}