白駿1092、倍加Greedy
https://www.acmicpc.net/problem/1092
1.アイデア
2)箱を該当するクレーンに移動できない
=>すべてのクレーンがチェックされている場合、経過時間+1
2.資料構造
ArrayList<Integer>
2個:各クレーンの最大重量リスト、各箱の重量リスト3.時間複雑度
コード#コード#
import java.io.*;
import java.util.*;
public class Main {
static int n; // 크레인 개수
static List<Integer> craneWeights = new ArrayList<>(); // 각 크레인의 최대 무게
static int m; // 박스 개수
static List<Integer> boxWeights = new ArrayList<>(); // 각 박스의 무게
static int minTime; // 출력, 최소 시간
static void solution() {
// 박스를 모두 옮길 수 없는 경우
if (boxWeights.get(0) > craneWeights.get(0)) {
minTime = -1;
return;
}
while (!boxWeights.isEmpty()) {
int boxIdx = 0;
for (int i = 0; i < craneWeights.size(); ) { // 주의) for 문에 i++ 없음
if (boxIdx == boxWeights.size()) // 마지막 박스까지 확인한 경우
break; // => 남은 첫 번째 박스, 첫 번째 크레인부터 다시 확인
if (boxWeights.get(boxIdx) <= craneWeights.get(i)) {
boxWeights.remove(boxIdx); // 해당 박스 옮김(제거)
i++; // 다음 크레인
}
else // [i] 크레인으로 박스 못 옮기는 경우
boxIdx++; // => [i] 크레인으로 다음 박스 옮길 수 있는지 확인
}
minTime++;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in)
);
StringTokenizer st;
n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++)
craneWeights.add(Integer.parseInt(st.nextToken()));
m = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < m; i++)
boxWeights.add(Integer.parseInt(st.nextToken()));
// 2개 리스트를 각각 무게 큰 순으로 정렬
// Collections.sort(craneWeights, (w1, w2) -> w2 - w1);
Collections.sort(craneWeights, Collections.reverseOrder());
Collections.sort(boxWeights, Collections.reverseOrder());
solution();
System.out.println(minTime);
}
}
Reference
この問題について(白駿1092、倍加Greedy), 我々は、より多くの情報をここで見つけました https://velog.io/@silver_star/백준-1092-배-Greedyテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol