백준 1092번: 배

백준 1092번: 배

아이디어

크레인의 무게 제한보다 무거운 박스는 옮길 수 없다. 한번에 최대한 많은 박스를 옮기려면, 가장 성능이 좋은 크레인이 가장 무거운 박스를 옮겨야 한다.
즉, 각 단계에서 가장 최선의 선택을 하는 그리디 알고리즘 문제이다.

코드

N = int(input())
crainList = list(map(int, input().split()))
M = int(input())
boxList = list(map(int, input().split()))

# 가장 "무거운" 박스부터 가장 성능이 좋은 크레인에 할당해줘야함
boxList.sort(reverse=True)
crainList.sort(reverse=True)

crainSize = len(crainList)
cnt = 0

# 가장 성능 좋은 크레인도 가장 무거운 박스를 옮길 수 없는 경우
if boxList[0] > crainList[0]:
    print(-1)

else:
    # boxList에 원소가 없을 때까지
    while boxList:
        crainIdx = 0
        i = 0
        while i < len(boxList):
            # 무서워서 남은 크레인으로 옮길 수 없는 경우
            if boxList[i] > crainList[crainIdx]:
                i += 1
                continue
            else:
                # 박스 제거, 인덱스 조절
                boxList.pop(i)
                i -= 1
                crainIdx += 1
                if crainIdx == crainSize:
                    break
            i += 1
        cnt += 1

    print(cnt)

주의점

같은 코드임에도 불구하고 Python3으로 제출하면 시간초과, Pypy3로 제출하면 통과가 된다. 혹시 Python3으로 작성한 코드가 시간초과가 난다면, Pypy3으로 다시한번 제출해보도록 하자.