[BOJ 1092] 배(그리디)

문제

[BOJ 1092] 배

크레인 N대를 이용해서 M개의 박스를 옮기는 최소시간 구하기 !!
(조건: 크레인은 동시에 움직임, 크레인 무게 제한보다 무거운 박스는 움직일 수 없음)

풀이

1. 박스 다 옮길 때까지, 2. 각각의 크레인에 대해, 3. 박스 탐색 (삼중 for문)

   ** 중요!
   여기까지만 구현하면 시간초과가 난다.
   박스는 내림차순으로 정렬되어있으므로, 한번 체크한 박스는 다시 체크할 필요가 없다.
   따라서 이를 indices배열로 관리한다.
   indices[i]: i번째 크레인이 탐색 시작할 박스의 인덱스

import sys
input = sys.stdin.readline

# 내림차순으로 정렬
N = int(input()) # 크레인의 수
cranes = list(map(int,input().split()))
cranes.sort(reverse=True)

M = int(input()) # 박스의 수
boxes = list(map(int,input().split()))
boxes.sort(reverse=True)

if cranes[0]<boxes[0]:
    print(-1)

else:  
    cnt = 0
    l1,l2 = len(boxes),len(cranes)
    check = [False]*l1
    indices = [0]*l2 
    time = 0
    while cnt<l1: 					# 1. 박스 다 옮길 때까지
        time += 1
        for c in range(l2): 				# 2. 각각의 크레인에 대해
            for b in range(indices[c],l1): 
                if check[b] or boxes[b]>cranes[c]: 	# 3. 옮길 수 없으면 인덱스 늘리기
                    indices[c] += 1
                else:
                    check[b]=True 
                    cnt += 1
                    break
    print(time)

삽질

1. 각각의 박스에 대하여, 2. 가벼운 박스면 able에 넣기 3. 다음 크레인 확인하기
   => 아래 코드는 len(able[c])가 가장 짧은 데에 넣어야 하는 것을 구현하기 까다로움

else:
    able = [ [] for _ in range(len(cranes)) ] # 크레인이 옮길 수 있는 박스들
    l1,l2 = len(boxes),len(cranes)
    b,c = 0,0
    while True: 			      # 1. 각각의 박스에 대하여
        if b==l1: break

        if boxes[b]<=cranes[c]: 	      # 2. 가벼운 박스면 able에 넣기
            able[c].append(boxes[b])
            b += 1

        if c==l2-1: c=0 		      # 3. 다음 크레인 확인하기
        else: c += 1

  print(max(len(a) for a in able))

느낀점

어려웠다. 그리디는 bfs처럼 큰 틀이 정해져있는 유형이 아니라서 구현력을 더 필요로 하는 것 같다. 그리디 유형 더 많이 풀어봐야겠다!!