백준 1092번: 배 (G5) - Python 풀이

문제 설명

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

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

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

입력

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

출력

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

예제 입력 1

3
6 8 9
5
2 5 2 4 7

예제 출력 1

2

예제 입력 2

2
19 20
7
14 12 16 19 16 1 5

예제 출력 2

4

예제 입력 3

4
23 32 25 28
10
5 27 10 16 24 20 2 32 18 7

예제 출력 3

3

예제 입력 4

10
11 17 5 2 20 7 5 5 20 7
5
18 18 15 15 17

예제 출력 4

2

문제 요약) 무게 제한을 가진 크레인으로 1분에 박스를 하나씩 배에 실을 수 있을 때, 모든 박스를 배로 옮기는 데 드는 시간의 최솟값을 구해라.

풀이 과정

우선 크레인과 박스 둘 다 내림차순 정렬을 시켜줬습니다.

모든 박스를 배로 옮기는 게 불가능한 경우에는 -1을 출력해야 하는데 그 상황은 무게 제한이 가장 큰 크레인으로도 못 옮기는 즉, 최대 무게 제한보다 무게가 큰 박스가 있을 때 발생합니다. 그래서 크레인의 최댓값과 박스의 최댓값을 비교해서 박스가 더 큰 경우에는 -1을 출력하고 종료합니다.

위의 경우가 아니라면 하나씩 살펴보면서 박스를 제거해 나가야 합니다. 각 크레인마다 박스의 값을 반복문으로 돌면서 크레인보다 작거나 같은 무게의 박스가 있으면 해당 박스를 제거하고, 바로 break로 반복문을 빠져나옵니다.

현재 크레인보다 값이 큰 박스가 나왔다면 뒤의 박스들을 더 봐야 합니다. 다만 이때 뒤의 박스 무게 중 최솟값보다도 현재 크레인이 작다면? → 어차피 이 크레인으로는 더 못 옮기니까 빠르게 다음 크레인을 확인하는 게 시간 절약을 할 수 있을 겁니다. 이 경우에도 break로 반복문을 빠져나옵니다. << 정확히 이 부분을 생각하지 못 해서 처음에 시간초과가 났습니다.

빠른 입력과 최소 무게도 못 드는 크레임일 때 바로 빠져나오는 코드를 추가해 정답을 맞힐 수 있었습니다.

정답 코드

# 빠른 입력
import sys
input = sys.stdin.readline 

# 크레인 입력 및 내림차순 정렬
N = int(input().strip())
crains = list(map(int, input().split()))
crains.sort(reverse=True)

# 박스 입력 및 내림차순 정렬
M = int(input().strip())
boxes = list(map(int, input().split()))
boxes.sort(reverse=True)

answer = 0

# 박스의 최댓값이 크레인의 최댓값보다 크다면
# 모든 박스를 배로 옮길 수 없는 것이니까 -1 출력
if crains[0] < boxes[0]:
    answer = -1
# 그게 아니라면 확인 들어갑니다~
else:
    # 박스가 모두 제거될 때까지 반복
    while boxes:
        # 크레인마다
        for i in range(len(crains)):
            # 박스를 순서대로 확인
            for j in range(len(boxes)):
                # 크레인으로 옮길 수 있는 박스면
                if crains[i] >= boxes[j]:
                    # 박스 제거 후 반복문을 빠져나와 다음 크레인을 확인
                    boxes.remove(boxes[j])
                    break
                # 현재 박스 boxes[j]를 현재 크레인 crains[i]으로 못 옮기는데,
                # 이 크레인이 최소 무게의 박스도 못 옮기는 거라면 이 크레인은 바로 패스
                elif crains[i] < boxes[-1]: # 이 반복문을 추가하는 것이 시간초과를 해결하는 핵심이었음!
                    break
        answer += 1
        
print(answer)

골드 5였지만 나쁘지 않았던 문제였습니다.

이상입니다.