[BOJ 1092] 배

    서론

    그리디 문제가 너무 재밌습니다. 

     

     

    1092번: 배

    첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보

    www.acmicpc.net

    문제

    지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.

    각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.
     

    입력

    첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

    출력

    첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.

     

    그리디 문제를 해결하기 위해서 2개의 조건을 충족하여야 합니다.

    1. 매 순간의 최적해를 고른다면 전체 최적해를 만족할 수 있는가? (Optimal substructure, 최적 부분 구조)
    2. 이전의 선택이 다음 선택에 영향을 끼치는가? (Greedy choice property, 탐욕 선택 속성)

    만약 두 가지의 조건을 만족한다면 그리디 알고리즘으로 해결할 수 있습니다.  그러나 문제를 받아들자마자 이러한 증명을 하기는 쉽지 않습니다. (특히 1번). 저 나름의 팁을 드리자면,

    문제에서 답의 조건을 제약하는 문장이 많다면 그리디 알고리즘인지 고려해본다. 

    고려하면서 극단적인 케이스를 고려하여 반례가 있는지 검증한다.

    정도로 요약할 수 있습니다.

     

    이번 문제에서는 각 크레인의 최대 하중보다 무거운 짐은 옮길 수 없다는 제약이 있습니다. 제약이 그닥 많지는 않아서 그리디로 파악하긴 쉽지 않지만, 2번 조건, 탐욕 선택 속성을 만족합니다. 한 크레인이 직전에 옮겼던 짐의 무게가 다음 운반할 짐의 무게에 영향을 미치지 않습니다.

     

    그렇다면 어떤 기준을 가지고 선택을 해야 최적해가 될 지 고민해봅니다.

     

    1. 가벼운 짐부터 공평하게 나눈다.

    반례는 간단합니다. 

    2

    1 10

    8

    1 1 1 1 10 10 10 10

    이 알고리즘대로라면 6을 출력하겠지만, 정답은 4가 되겠죠.

     

    2. 각 크레인이 들 수 있는 최대 무게에 가까운 짐부터 가져간다.

    마땅한 반례가 생각이 나질 않아서 답인 것 같이 보이지만 이 구현으로 틀렸습니다.

     

    3. '동시에' 작동하는 조건을 무시하고, 가장 적은 일을 한 크레인부터 자기 덩치에 맞는 일감을 가져간다.

    이 풀이로 AC를 얻어냈습니다. 박스를 무게 내림차순으로 정렬한 다음, 각 크레인이 일감을 가져가는데 이 크레인은 priority queue에 정렬되어 있으며, 그 기준은 1. 가장 적은 일을 한 크레인 2. 힘이 강한 크레인 순으로 정렬을 합니다. 그 중 가장 많은 일을 한 크레인이 운반한 박스 갯수가 정답이 될 것입니다.

     

     

    코드

    import java.io.*;
    import java.util.*;
    
    public class Main {
    
    	public static void main(String[] args) throws Exception{
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		
    		int N = Integer.parseInt(br.readLine());
    		Integer[][] crane = new Integer[N][2];
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		for(int i = 0; i < N; i++) {
    			crane[i][0] = Integer.parseInt(st.nextToken());
    			crane[i][1] = 0;
    		}
    		Comparator<Integer[]> cpr = new Comparator<Integer[]>() {
    
    			@Override
    			public int compare(Integer[] o1, Integer[] o2) {
    				if(o1[1] != o2[1]) {
    					return Integer.compare(o1[1], o2[1]);
    				}
    				return Integer.compare(o1[0],o2[0]);
    			}
    			
    		};
    		Arrays.sort(crane, cpr);
    		
    		int M = Integer.parseInt(br.readLine());
    		Integer[] boxes = new Integer[M];
    		st = new StringTokenizer(br.readLine());
    		for(int i = 0; i < M; i++) {
    			boxes[i] = Integer.parseInt(st.nextToken());
    			if(boxes[i] > crane[N-1][0]) {
    				System.out.println("-1");
    				System.exit(0);
    			}
    		}
    		Arrays.sort(boxes, (o1,o2)->(Integer.compare(o2, o1)));
    		for(int i = 0; i < M; i++) {
    			int curr = boxes[i];
    			for(Integer[] ia : crane) {
    				if(ia[0] >= curr) {
    					ia[1]++;
    					Arrays.sort(crane, cpr);
    					break;
    				}
    			}
    		}
    		int answer = 0;
    		for(Integer[] ia : crane) {
    			answer = Math.max(answer, ia[1]);
    		}
    		System.out.println(answer);
    //		System.out.println(Arrays.toString(crane));
    //		System.out.println(Arrays.toString(counting));
    		br.close();
    	}
    }

     

    'IT > Algorithm' 카테고리의 다른 글

    [Java] 알고리즘 PS에 적용할만한 짱짱빠른 I/O  (0) 2021.08.07
    [BOJ 9375] 패션왕 신해빈  (0) 2021.03.04
    [BOJ 17839] Baba is Rabbit  (0) 2021.03.04
    [BJ 3344] N-Queens  (0) 2021.02.24
    [BJ 18768] 팀 배정  (0) 2021.02.23

    댓글