📚 1092 - 배

배

이해

처음에는 내림 차순 정렬하여 문제를 풀려고 했다.
크레인에 큰 것부터 넣기
다만, 이와 같은 반례가 있다.

4 3 2 1
1 1 2 2 3 3 4 4

크기 4인 박스를 크레인에 넣고, 그 다음 크기 3인 박스를 크레인에 넣어야 한다.

소스

import sys  
  
read = sys.stdin.readline  
  
n = int(read())  
  
crain = list(map(int, read().split()))  
  
m = int(read())  
  
weight = list(map(int, read().split()))  
  
crain.sort()  
weight.sort()  
answer = 0  
  
if max(weight) > max(crain):  
    print(-1)  
else:  
    up = 0  
    answer = 0  
    while up != m:  
        answer += 1  
        cr_idx = n - 1  
        for i in range(m - 1, -1, -1):  
            # 방문한 곳이라면 continue            
				if weight[i] == 0:  
                continue  
            if cr_idx == -1:  
                break  
            if weight[i] <= crain[cr_idx]:  
                cr_idx -= 1  
                up += 1  
                # 방문한 곳은 0으로 체크  
                weight[i] = 0  
  
    print(answer)