[Gold V] 배 - 1092
성능 요약
메모리: 15180 KB, 시간: 284 ms
분류
그리디 알고리즘, 정렬
제출 일자
2024년 6월 16일 20:34:37
문제 설명
지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.
각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.
접근 방법
1. 각 크레인이 옮길 수 있는 무게를 역순으로 정렬 시켜준다.
2. 리스트를 순회하며 각 크레인이 옮길 수 있는 최대 무게들을 옮겨준다.
3. 시간 복잡도는 O(N * M) + 정렬 시간으로 충분함
풀이 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/**
* 문제: BOJ_1092_G5_배
* 메모리: 15180KB
* 시간: 284ms
* 접근 방법
* 1. 각 크레인이 옮길 수 있는 무게를 역순으로 정렬 시켜준다.
* 2. 리스트를 순회하며 각 크레인이 옮길 수 있는 최대 무게들을 옮겨준다.
* 3. 시간 복잡도는 O(N * M) + 정렬 시간으로 충분함
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
ArrayList<Integer> crane= new ArrayList<>();
// Input
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
crane.add(Integer.parseInt(st.nextToken()));
}// Input End
// Input
int M = Integer.parseInt(br.readLine());
ArrayList<Integer> box = new ArrayList<>();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
box.add(Integer.parseInt(st.nextToken()));
}// Input End
box.sort(Collections.reverseOrder());
crane.sort(Collections.reverseOrder());
if (crane.get(0) < box.get(0)) {
System.out.println(-1);
return;
}
int t = 0;
while (!box.isEmpty()) {
int craneIdx = 0, boxIdx = 0;
int boxSize = box.size();
while (craneIdx < N && boxIdx < boxSize) {
if(crane.get(craneIdx) >= box.get(boxIdx)) {
box.remove(boxIdx);
boxSize--;
craneIdx++;
}else{
boxIdx++;
}
}
t++;
}
System.out.println(t);
}
}
'알고리즘 - Baekjoon > Gold' 카테고리의 다른 글
[백준] 10282번 : 해킹 Gold4(골드4) - JAVA[자바] (1) | 2024.06.18 |
---|---|
[백준] 1253번 : 좋다 Gold4(골드4) - JAVA[자바] (0) | 2024.06.18 |
[백준] 2229번 : 조 짜기 Gold5(골드5) - JAVA[자바] (1) | 2024.06.16 |
[백준] 20208번 : 진우의 민트초코우유 Gold5(골드5) - JAVA[자바] (0) | 2024.06.15 |
[백준] 22866번 : 탑 보기 Gold3(골드3) - JAVA[자바] (1) | 2024.06.14 |