[BOJ] 배 (1092, G5)

https://www.acmicpc.net/problem/1092

 

엄청나게 삽질한 문제...

1차 시도 / 가장 무거운 것과, 가장 가벼운 것을 동시에 실어 날라주는 생각을 했지만... 테케부터 걸린다.
아마, 중간 무게에서 효율성을 놓친 것으로 보인다.

2차 시도 / 가장 무거운걸 실어보내는거로 생각..? 하지만 놀아버리는 크레인이 나오면 안된다.

3차 시도 / 현재 크레인이 실을 수 있는 가장 무거운 것을 찾자.
단, 현재 크레인이 가망이 없으면 탐색해봤자 라는 걸 걸러내야 효율적이다.!

import sys
input = sys.stdin.readline

crane_num = int(input())
crane_list = list(map(int, input().split()))
crane_list.sort(reverse = True)

box_num = int(input())
box_list = list(map(int, input().split()))
box_list.sort(reverse = True)

# 불가능 판단부터, 하나라도 못 실으면 탈락이니까. 그냥 이거로 됨.
if crane_list[0] < box_list[0]:
    print(-1)
else:
    time = 0
    # 실을 수 있다.
    while box_list:
        for cur_crane in crane_list:
            # 가망도 없다면 돌지 마라
            if box_list and cur_crane < box_list[-1]:
                continue
            else:
                for cur_box in box_list:
                    if cur_crane >= cur_box:
                        # 현재 실을 수 있는 가장 최고의 무게를 실자
                        box_list.remove(cur_box)
                        #  박스를 실으면, 박스를 더 안봐도 되게 함
                        break
        # 라운드 종료
        time += 1
    print(time)