문제
지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.
각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.
생각
- 무게제한이 큰 크레인이 항상 가장 큰 박스를 가져가도록 한다.
- 예외사항이 없으므로 Greedy로 풀 수 있는 문제다.
Solution 1
import sys
input = sys.stdin.readline
n = int(input())
cranes = sorted(map(int, input().split()), reverse=True)
m = int(input())
boxes = sorted(map(int, input().split()), reverse=True)
def moveCrane():
for crane in cranes:
for i, box in enumerate(boxes):
if crane < box: continue
del boxes[i]
break
def solve():
if cranes[0] < boxes[0]: return -1
result = 0
while boxes:
moveCrane()
result += 1
return result
print(solve())Solution 2
1번 풀이로 제출해서 통과는 됐으나,
시간이 2000ms 이상 걸리는 등 효율적이라고 보긴 어려웠다.
시간을 단축할 방법을 고민하던 차에, 관점 자체를 반대로 해봤다.
1번 풀이는 크레인에게 최적의 박스를 할당하겠다는 그림이다.
크레인마다 자신이 처리할 수 있는 가장 큰 박스를 찾아야 한다.
그렇다면 반대로, 박스를 최적의 크레인에게 주겠다는 관점으로 한다면?
크레인은 박스를 처리하기만 하고, 애초에 줄 때부터 항상 최적 대상에게 주는 것이다.
결론적으로 같은거 아닌가 싶겠지만, 최적 조건을 따지는 대상이 달라진다.
최적 크레인 조건
1. 박스 무게가 크레인 무게제한을 넘지 않을 것.
2. 처리한 박스 수가 크레인 중 가장 적을 것. (여러 개일 시 무게제한이 더 작은 것)
counts 라는 배열에 크레인마다 처리한 박스 수를 저장한다.
박스가 가장 많은 크레인의 박스 수가 즉 최소 시간이 되겠다.
import sys
input = sys.stdin.readline
n = int(input())
cranes = sorted(map(int, input().split()), reverse=True)
m = int(input())
boxes = sorted(map(int, input().split()), reverse=True)
counts = [0]*n
def serveBox(box):
candidate = 0
for i, crane in enumerate(cranes):
if crane < box: break
if box <= crane and counts[i] < counts[candidate]:
candidate = i
counts[candidate] += 1
def solve():
if cranes[0] < boxes[0]: return -1
for box in boxes:
serveBox(box)
return max(counts)
print(solve())Java ver.
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
Integer[] cranes = new Integer[n];
for (int i=0; i<n; i++) {
cranes[i] = scanner.nextInt();
}
int m = scanner.nextInt();
Integer[] boxes = new Integer[m];
for (int i=0;i<m;i++) {
boxes[i] = scanner.nextInt();
}
scanner.close();
Arrays.sort(cranes, Collections.reverseOrder());
Arrays.sort(boxes, Collections.reverseOrder());
int[] counts = new int[n];
System.out.println(solve(cranes, boxes, counts));
}
private static int solve(Integer[] cranes, Integer[] boxes, int[] counts) {
if (cranes[0] < boxes[0]) {
return -1;
}
for (Integer box: boxes) {
serveBox(cranes, box, counts);
}
return getMaxCount(counts);
}
private static int getMaxCount(int[] counts) {
int result = 0;
for (int count: counts) {
if (count < result) continue;
result = count;
}
return result;
}
private static void serveBox(Integer[] cranes, Integer box, int[] counts) {
int candidate = 0;
for (int i=0; i<cranes.length; i++) {
Integer crane = cranes[i];
if (crane < box) continue;
if (counts[candidate] < counts[i]) continue;
candidate = i;
}
counts[candidate]++;
}
}