출처
https://www.acmicpc.net/problem/1092
1092번: 배
첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보
www.acmicpc.net
결과
첫 번째 풀이
두 번째 풀이
문제
지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.
각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.
예제 입력
3
6 8 9
5
2 5 2 4 7예제 출력
2해석
하나의 크레인은 하나의 화물을 배에 실을 수가 있습니다. 모든 크레인들이 동시간에 움직인다고 가정하여 최단 시간에 모든 화물들을 배에 실도록 하는 문제입니다. 우선적으로 해야할 것은, 크레인들 중에서 가장 무거운 하중을 들 수 있는 크레인이 가장 무거운 화물을 들도록 크레인과 화물들을 정렬하는 것입니다. 만약, 정렬한 이후, 가장 무거운 하중을 들 수 있는 크레인이 가장 무거운 화물을 들 수 없다면, 바로 -1을 출력합니다. 그렇지 않다면 모든 크레인들(crane 리스트)을 이용하여 화물들(boxes 리스트)을 옮길 것입니다.
첫 번째 풀이. (Pypy3 정답, Python3 시간 초과)
일단, 화물들 중에서 옮겨졌는지 알려주는 리스트인 vi를 생성하였습니다. 아직 옮겨지지 않은 화물은 True값을 갖고, 옮겨진 화물은 False값을 갖게 하였습니다. crane은 for구문을 통하여 한 개씩 크레인을 사용하며, 화물들을 확인하는 boxes 리스트도 for구문을 사용한다면 크레인을 바꿔 갈 때마다 매번 화물 인덱스를 0부터 확인해야 하므로 while구문을 사용하였습니다. 그렇게 하여 만약 크레인이 화물을 들수 있고 아직 옮겨지지 않은 화물이라면 (위치 확인 리스트의 값이 True) 화물 위치 확인값은 False로 바꿔주고 다른 크레인을 사용하여 인덱스 값이 m이 될 때까지 확인합니다. 그렇게 하여 답을 구하면 됩니다.
결과는 Pypy3에서는 정답이지만, Python3에서는 시간 초과가 떴습니다.
소스 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
import sys
n = int(sys.stdin.readline())
crane = sorted(list(map(int, sys.stdin.readline().strip().split())), key=lambda x:x, reverse=True)
m = int(sys.stdin.readline())
boxes = sorted(list(map(int, sys.stdin.readline().strip().split())), key=lambda x:x, reverse=True)
vi = list(True for _ in range(m))
answer = 0
if boxes[0] > crane[0]:
print(-1)
else:
while any(vi):
idx = 0
for cont in crane:
while idx < m:
if cont >= boxes[idx] and vi[idx]:
vi[idx] = False
idx += 1
break
idx += 1
answer += 1
print(answer)
|
cs |
두 번째 풀이. (Python3 정답)
크레인이 마지막에 화물을 옮기고 멈춘 위치를 알려주는 리스트(position)를 추가하였습니다. 처음에는 모든 크레인의 위치가 0에 있고 리스트의 크기는 n입니다. 이젠, boxes의 while구문이 필요가 없게 되었습니다. 모든 크레인이 0의 위치에서 끝까지 이동할 때까지 while문을 실행하면 됩니다. 위처럼 크레인은 for구문을 이용하여 하나씩 확인합니다. 그리고, 크레인이 옮길 수 있는 화물(화물의 확인값이 True이고, 크레인의 값이 화물값보다 클 때)이라면 화물 확인값은 False로 변경시키고 다른 크레인을 확인한다. 만약 크레인이 옮길 수 없다면 그 크레인의 위치(position)를 옮길 수 있는 화물이 나오거나 위치가 m이 될 때까지 움직여줍니다. 이러한 방식으로 답을 구할 수 있습니다.
소스 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
import sys
n = int(sys.stdin.readline())
crane = sorted(list(map(int, sys.stdin.readline().strip().split())), key=lambda x:x, reverse=True)
m = int(sys.stdin.readline())
boxes = sorted(list(map(int, sys.stdin.readline().strip().split())), key=lambda x:x, reverse=True)
# 옮겨 졌는지 확인을 위한 boxes 크기의 리스트를 만든다
vi = list(True for _ in range(m))
position = list(0 for _ in range(n))
answer = 0
if boxes[0] > crane[0]:
print(-1)
else:
# 모든 화물을 옮길 때 까지(하나라도 vi에 True값이 있다면 while문 실행)
while any(vi):
for cont in range(len(crane)):
# 각각의 컨테이너가 m의 위치까지 갈 때까지 실행
while position[cont] < m:
# 만약 옮길 수 있는 화물이 생긴다면 position[cont]위치에서 한 칸 움직이고 멈추게 된다.
if crane[cont] >= boxes[position[cont]] and vi[position[cont]]:
vi[position[cont]] = False
break
position[cont] += 1
answer += 1
print(answer)
|
cs |
'백준 > lv.4' 카테고리의 다른 글
| [lv4] 7662. 이중 우선순위 큐(Python 파이썬 풀이) (0) | 2021.08.07 |
|---|---|
| [lv4] 1016. 제곱 ㄴㄴ수 (Python 파이썬 풀이) (0) | 2021.02.13 |