[Baekjoon] 1092번 : 배

1. 문제

https://www.acmicpc.net/problem/1092

• 그리디 문제

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

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

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

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

// 예제 입력 1
3
6 8 9
5
2 5 2 4 7

// 예제 출력 1
2

// 예제 입력 2
2
19 20
7
14 12 16 19 16 1 5

// 예제 출력 2
4

// 예제 입력 3
4
23 32 25 28
10
5 27 10 16 24 20 2 32 18 7

// 예제 출력 3
3

// 예제 입력 4
10
11 17 5 2 20 7 5 5 20 7
5
18 18 15 15 17

// 예제 출력 4
2

2. 핵심 아이디어

• 박스를 무게 기준으로 내림차순 정렬한 뒤에, 무거운 것부터 옮기도록 함
• 시간 복잡도 O(NM)에 문제를 해결할 수 있음
• 크레인과 박스를 내림차순 정렬
• 매 분마다, 모든 크레인에 대하여 옮길 수 있는 박스를 선택하여 옮기도록 함

3. Python 문제풀이

import sys
input = sys.stdin.readline

n = int(input())
cranes = list(map(int, input().split()))
m = int(input())
boxes = list(map(int, input().split()))

# 모든 박스를 옮길 수 없는 경우
if max(cranes) < max(boxes) :
  print(-1)
  sys.exit()

# 각 크레인이 현재 옮겨야 하는 박스의 번호 (0부터 시작)
positions = [0] * n
# 각 박스를 옮겼는지 여부
checked = [False] * m
# 최적의 해를 구해야 하므로, 내림차순 정렬
cranes.sort(reverse = True)
boxes.sort(reverse = True)

result = 0
count = 0

while True :
  # 박스를 다 옮겼다면 종료
  if count == len(boxes) :
    break
  # 모든 크레인에 대하여 각각 처리
  for i in range(n) :
    while positions[i] < len(boxes) :
      # 아직 안 옮긴 박스 중에서, 옮길 수 있는 박스를 만날 때까지 반복
      if not checked[positions[i]] and cranes[i] >= boxes[positions[i]] :
        checked[positions[i]] = True
        positions[i] += 1
        count += 1
        break
      positions[i] += 1
  result += 1

print(result)

4. Java 문제풀이

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    ArrayList<Integer> cranes = new ArrayList<>();

    for (int i=0; i<n; i++) {
      cranes.add(sc.nextInt());
    }

    Collections.sort(cranes, Collections.reverseOrder());
    int m = sc.nextInt();
    ArrayList<Integer> boxes = new ArrayList<>();

    for(int i=0; i<m; i++) {
      boxes.add(sc.nextInt());
    }

    Collections.sort(boxes, Collections.reverseOrder());

    if (cranes.get(0) < boxes.get(0)) System.out.println("-1");
    else {
      int result = 0;
      while (!boxes.isEmpty()) {
        int idx = 0;
        for (int i=0; i<cranes.size();) {
          if (idx == boxes.size()) break;
          else if (cranes.get(i) >= boxes.get(idx)) {
            boxes.remove(idx);
            i++;
          }
          else idx++;
        }
        result++;
      }
      System.out.println(result);
    }
  }
}