[파이썬 | BOJ | 1092] 배

https://www.acmicpc.net/problem/1092

1092번: 배

문제

지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.

각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.

풀이

deque을 만들어서, 우리가 머릿속으로 생각하는것과 같이 알고리즘을 구성해서 문제를 해결하였다.

일단 crane과 box를 모두 내림차순으로 정렬한다. ( deque은 sorting이 불가능해서 list로 sorting후 변환함 ) 

 

그러면 box deque의 맨 왼쪽에 날라야할 박스중에서 가장 큰 값이 있을 것이다.

 

일단 box deque의 맨 왼쪽값( 가장 큰 값 )이 크레인이 나를 수 있는 가장 큰 값보다 크다면 무조건 답은 -1을 출력한다.

 

그 외의 경우를 생각하면,

반복문을 돌면서, box deque의 맨 왼쪽값( 가장 큰 값 )이 크레인의 가장 큰값보다 작다면, 무조건 그 박스를 그 크레인에 걸어야 한다.

 

따라서 해당 박스를 pop해서 container에 넣는다.

 

이제 새로운 box deque의 맨 왼쪽값에는 방금 container에 넣은 값보다는 작거나 같은 새로운 박스가 위치한다.

이 박스는 중간 크레인보다 작아야하며, 만약 이 박스의 크기가 중간 크레인보다 크다면 현재로써는 배로 옮길수가 없다. 따라서 이 박스는 pop해서 temp에 넣는다.

 

위를 반복해서, box deque의 맨 왼쪽에 있는 값이 중간 크레인보다 작다면, pop해서 container에 넣는다.

 

이제 새로운 box deque에 맨 왼쪽값에는 방금 container에 넣은 값보다는 작거나 같은 새로운 박스가 위치한다.

이 박스는 제일 작은 크레인보다 작아야하며, 만약 이 박스의 크기가 제일 작은 크레인보다 크다면 현재로써는 배로 옮길수가 없다.

따라서 이 박스는 pop해서 temp에 넣는다

 

위를 반복해서, box deque의 맨 왼쪽에 있는 값이 제일작은 크레인보다 작다면, pop해서 container에 넣는다.

 

이제 container에 N개가 차게 되면, 모든 크레인이 동작한다는 뜻이며, 배로 옮기게 되고 count를 + 1 해서 세준다.

그리고나서 container는 비우고, temp에 있는 값도 다시 deque으로 옮겨준다.

 

설명이 복잡하니 예를 들어보자

 

3
6 8 9
9
1 2 3 4 5 6 7 8 9

인 input이 있으면,

 

반복문	box deque	container list	temp list
1회차	deque([8, 7, 6, 5, 4, 3, 2, 1])	[9]	[]
2회차	deque([7, 6, 5, 4, 3, 2, 1])	[9, 8]	[]
3회차	deque([6, 5, 4, 3, 2, 1])	[9, 8]	[7]
4회차	deque([5, 4, 3, 2, 1])	[9, 8, 6]	[7]
5회차	deque([7, 5, 4, 3, 2, 1])
6회차	deque([5, 4, 3, 2, 1])	[7]	[]
7회차	deque([4, 3, 2, 1])	[7, 5]	[]
8회차	deque([3, 2, 1])	[7, 5, 4]	[]
9회차	deque([3, 2, 1])
10회차	deque([2, 1])	[3]	[]
11회차	deque([1])	[3, 2]	[]
12회차	deque([])	[3, 2, 1]	[]

 으로 진행된다.

 

 

# [파이썬 | BOJ | 1092] 배
import sys
from collections import deque
read = sys.stdin.readline
 
N = int(read())
crane = list(map(int, read().split()))
M = int(read())
box = list(map(int, read().split()))
 
crane.sort(reverse=True)
box.sort(reverse=True)
box = deque(box)
container = []
temp = []
ans = 0
 
while box or temp:
    if not box and len(container) != N:
        container.clear()
        ans += 1
        box.extendleft(reversed(temp))
        temp.clear()
        #print(box)
 
    if len(container) == N:
        container.clear()
        ans += 1
        box.extendleft(reversed(temp))
        temp.clear()
        #print(box)
 
    if box[0] > crane[0]:
        print(-1)
        sys.exit(0)
    
    if crane[len(container)] >= box[0]:
        container.append(box.popleft())
    
    else:
        temp.append(box.popleft())
    #print(box, container, temp)
 
print(ans+1)