[BOJ 1092] 배

대연.

·

2021. 3. 4. 20:22

서론

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

 

 

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();
	}
}

 

'프로그래밍 > Algorithm' 카테고리의 다른 글

[Java] 알고리즘 PS에 적용할만한 짱짱빠른 I/O  (0) 2021.08.07
[BOJ 9375] 패션왕 신해빈  (0) 2021.03.04
[BOJ 1092] 배  (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

0개의 댓글