[백준 19598번] 배 문제 풀이

 

 

< 문제 >

 

 

< 입출력 >

 

 

 

 

 

TRY 1   - 틀렸습니다.

 

: 박스는 heapq에 넣어 놓고, 크레인의 개수만큼 꺼내어 크레인의 한계 무게와 비교하여 옮기지 못하는 경우에는 다시 heapq에 넣었다. (단, 크레인의 개수보다 남아있는 박스가 더 적은 경우를 고려해서, if 문을 통해 남아있으면 꺼내야 한다.)

heapq가 빌 때까지 반복하여 옮기는데 걸리는 시간을 구한다.

 

하지만, heapq를 통해 남은 박스를 고르면 작은 순서 부터 나와서 한 번의 기회에 더 많은 박스를 옮길 수 있는 조합이 아닐 수 있다는 점을 간과했다. 

import sys
import heapq
input = sys.stdin.readline

N = int(input())
crane = list(map(int, input().split()))
M = int(input())
box = list(map(int, input().split()))

left = []                   # 아직 옮겨지지 않고 남아있는 박스 배열
for i in box:               # 옮겨지지 않은 박스 초기화
    heapq.heappush(left, i)

crane.sort()                # 크레인 오름차순으로 정렬
time = 0                    # 옮기는데 걸리는 시간


if max(crane) < max(box):   # 크레인이 옮길 수 있는 가장 큰 무게보다 박스의 무게가 더 큰 경우 -1 출력
    print(-1)
else:
    while len(left) > 0:    # 남아 있는 박스가 있을 때까지
        time += 1
        take = []
        for i in range(len(crane)):   # 일단 크레인의 개수만큼 남아있는 박스 배열에서 꺼낸다
            if len(left)>0:
                take.append(heapq.heappop(left))
        take.sort()
        crane_num = len(crane) - 1           # 아직 박스를 담지 않은 크레인 중 가장 한계가 넓은 크레인
        for i in range(len(take)):                    # 꺼낸 박스에서 크레인의 무게 제한과 비교
            if take[len(take) - i -1] > crane[crane_num]:     # 박스가 크레인의 한계 무게보다 큰 경우
                heapq.heappush(left, take[len(take) - i -1])  # 다시 옮겨지지 않고 남아 있는 박스 배열에 추가한다
            else:
                if crane_num >0:        # 해당 크레인은 썼으므로, 아직 박스를 담지 않은 크레인 중 가장 한계가 넓은 크레인 바꿔주기
                    crane_num -= 1
    print(time)

 

 

 

 

TRY 2 - 성공

 

:  박스와 크레인을 모두 내림차순 한뒤, 박스의 개수만큼 앞에서 부터 크레인이 옮길 수 있는 박스의 위치를 찾는다.

시간 초과를 위해 position 배열을 활용하여, 무거워서 박스를 못옮겼을 때, position + 1을 해주어, 다음에는 그 박스 다음 박스부터 시행하게 한다.

import sys
input = sys.stdin.readline

n = int(input())
crane = list(map(int, input().split()))
m = int(input())
box = list(map(int, input().split()))

crane.sort(reverse=True)    # 내림차순 정렬
box.sort(reverse=True)

count = 0    # 옮긴 박스의 개수
time = 0     # 옮기는 데 걸린 박스의 개수
position = [0] * n   # 시간 초과 방지로 각 크레인이 어느 박스부터 비교할지 저장
checked = [0] * m    # 옮긴 박스인지 여부

if max(box) > max(crane):
    print(-1)
else:
    while count < len(box):
        for i in range(n):
            while position[i] < len(box):    # 크레인이 들 수 있는 박스가 나올때 까지 찾기
                if crane[i] >= box[position[i]] and checked[position[i]] == 0:
                    count += 1
                    checked[position[i]] = True
                    position[i] += 1
                    break
                else:
                    position[i] += 1

        time += 1

    print(time)