[ 백준 1092 ] 배 - Python

문제 보기

이 문제는 그리디 문제이다.

 

크레인을 통해서 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구해야 한다.

 

크레인의 값과 박스의 값을 무작위가 아닌 큰 값부터 순차적으로 진행하는 것이 가장 효율적이라고 생각하였다. 

 

알고리즘 구현 과정은 아래와 같다.

1. 크레인과 박스 값을 내림차순으로 정렬한다.

2. 상자를 옮겼는지 확인하기 위한 Flag 배열을 추가하였다.

3. 모든 크레인 값을 순회하면서 해당 크레인이 옮길 수 있는 가장 큰 상자를 옮기고 Flag 값을 1로 업데이트한다.

4. 모든 Flag 값이 1이면(Count = M) 반복문을 종료한다.

 

추가적으로 상자의 값을 크레인이 담을 수 없는 경우는 모든 박스를 배로 옮길 수 없으므로 따로 처리하였다!

 

코드

from collections import defaultdict


if __name__ == "__main__":
    # inputs
    N = int(input())  # 크레인 갯수
    crane = list(map(int, input().split()))
    M = int(input())  # 상자 갯수
    box = list(map(int, input().split()))

    # 내림차순 정렬
    crane.sort(reverse=True)
    box.sort(reverse=True)

    # 탐색 시작(그리디)
    if max(box) > max(crane):  # 담을 수 없는 경우
        print(-1)
    else:
        answer = 0
        # 각 크레인이 담을 수 있는 상자 정보 저장
        crane_dic = defaultdict(list)
        for i in range(N):
            for j in range(M):
                if crane[i] >= box[j]:
                    crane_dic[crane[i]].append(j)

        # 탐색
        answer = 0
        count = 0
        box_flag = [0] * M
        while count != M:
            answer += 1
            for i in range(N):
                for j in crane_dic[crane[i]]:
                    if box_flag[j] == 0:
                        box_flag[j] = 1
                        count += 1
                        break
        print(answer)