백준 1092 : 배 (Python)

본문 링크

import sys
input=sys.stdin.readline

N=int(input())
N_list=sorted(list(map(int,input().split())))

M=int(input())
M_list=sorted(list(map(int,input().split())))

if N_list[-1]<M_list[-1]:
    print(-1)
    exit(0)
count=0
while True:
    for i in range(-1,-N-1,-1):
        P = -1
        if len(M_list)>0:
            while True:
                if N_list[i]>=M_list[P]:
                    del M_list[P]
                    break
                elif -P==len(M_list) or len(M_list)==0:
                    break
                elif N_list[i]<M_list[P]:
                    P-=1
    count+=1
    if len(M_list)==0:
        print(count)
        break

📌 어떻게 접근할 것인가?

크레인을 박스를 처리하는 시간의 최소값을 구하는 문제이다.
가만히 생각해보면 매번 크레인이 들수있는 가장 큰 박스를 처리하면 가장 빠르지않을까?
라는 아이디어가 떠올랐고 바로 구현해주었다.

N_list 와 M_list 를 정렬해준다.
만약 가장 무거운 박스를 처리할수있는 크레인이 가장 무거운 박스보다 값이 작다면 -1을 출력하고 코드를 중지한다.

그렇지않다면 완전탐색을 사용해서 크레인이 들수있는 가장 큰 박스를 찾을때마다 그 박스를 pop() 함수로 지워준다.
만약 박스가 너무 크다면 인덱스 값을 조정해서 더 작은 박스를 찾는다.

거의 3중 반복문이라서 시간초과가 걱정되었는데 $N$ 과 $M$ 의 범위가 $1≤N≤50 , 1≤M≤10000$ 이라서 완전탐색이 가능했다.

✅ 코드에서 주의해야할 부분

• 크레인과 박스 리스트는 정렬해준다.
• 박스의 개수가 0 이상인지 매번 확인해준다