[BAEKJOON] 1092 배

문제 요약

• 알고리즘 분류: 그리디, 정렬
• 난이도:Gold5
• 문제내용:
  • 크래인 N개와 박스 M개가 있다. 각 크레인은 최대 들수 있는 무게와 박스별 무개가 주어진다.
  • 1분당 한 크래인은 한개만 옮길수있다.
  • 모든 박스를 옮기는데 걸리는 시간을 구해라.

• 사이트: https://www.acmicpc.net/problem/1092

1092번: 배

문제풀이

 이번 문제는 그리디문제인데, 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디에 설명은 밑에 사이트에 참조하면된다.

https://jih3508.tistory.com/70

[알고리즘 이론] 그리디(Greedy)

 문제 접근 방법

 이번 문제에서 푸는 방법은 무거운 순으로 옮겨 버리면 된다. 무게 순으로 옮겨 버리면 각 크레인의 최대 들수 있는 박스 순으로 옮겨야 최대한 많이 옮길수가 있다. 그러면 무거운 순으로 옮겨서 처리하면 O(NM)이라는 시간 복잡도가 나올것이다.

1. 박스, 크래인을 내림차순으로 정렬한다.
2. 각 크래인 마다 들수 있는 박스중 가장 무거운 순서대로 선택하도록 한다.(이 부분 구현 하는게 중요함)

 말로는 쉬운데 2번은 부분을 구현하는게 쉽지는 않을수 있다. 하지만 코드를 디버깅해서 보면 이해가 될수가 있다.

Code

Python

N = int(input())
cranes = sorted(list(map(int, input().split())), reverse= True)

M = int(input())
boxs = sorted(list(map(int, input().split())), reverse= True)

if cranes[0] < boxs[0]: 
    print(-1)
    exit()

position = [0] * N # 각 크레인이 현재 옮겨야 하는 박스의 번호(0부터 시작)
checked = [False] * M # 박스 옮겨는지 체크
result = 0

while True:
    if sum(checked) == M: break
    # 이번 타임에 각 크레인 실을수 있는 박스 조사 
    for i in range(N):
        while position[i] < M:
            # 남은 박스중 옮길수 있는 박스 선택
            if not checked[position[i]] and cranes[i] >= boxs[position[i]]:
                checked[position[i]] = True
                position[i] += 1
                break
            position[i] += 1
    result += 1

print(result)

Java

 Java는 파이썬 보다 구현 하기가 힘들수가 있다. 왜나하면 내림차순 정렬이 일반 타입의 배열에서는 지원이 안되서 정수형 배열을 부분은 Integer객체형 배열로 선언하면 역순으로 정렬이 가능하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

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());
		StringTokenizer st = new StringTokenizer(br.readLine());
		Integer[] cranes = new Integer[N];
		for(int i = 0; i < N; i++) {
			cranes[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(cranes, Collections.reverseOrder());
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		Integer[] boxs = new Integer[M]; // collection 함수 사용하기 위해서 객체형으로 선언
		for(int i = 0; i < M; i++) {
			boxs[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(boxs, Collections.reverseOrder());
		//
		if(boxs[0] > cranes[0]) {
			System.out.println(-1);
			System.exit(0);
		}
		int[] position = new int[N]; // 각 크레인이 현재 옮겨야 하는 박스의 번호(0부터 시작)
		boolean[] checked = new boolean[M]; // 박스 옮겨는지 체크
		int count = 0;
		int result = 0;
		while (true){
			if( count == M) break;
			// 이번 타임에 각 크레인 실을수 있는 박스 조사 
			for(int i = 0; i < N; i++) {
				while (position[i] < M) {
					if(!checked[position[i]] && cranes[i] >= boxs[position[i]]) {
						count++;
						checked[position[i]] = true;
						position[i]++;
						break;
					}
					position[i]++;
				}
			}
			result++;
		}
		System.out.println(result);
	}
		
}