[백준] 1092번 : 배

1092번: 배

1092번: 배

📄 문제개요

• 항구에 크레인이 있고, 최대 박스를 들 수 있는 크레인이 주어지고, 모든 크레인이 동시에 박스를 옮기는데 걸리는 시간은 1분이다. 박스와 크레인이 주어졌을때, 옮길 수 있는 최소 시간을 구하여라.

🤔 문제분석

• 크레인과 박스를 내림차순 으로 정렬한다.
• 박스를 순회하면서, 크레인이 박스를 제거시킨다.
  • 박스를 제거시킬때 크레인은 자기가 옮길 수 있는 최대의 무게를 그순간 옮겨야한다.
• O(M^2*N)으로 문제를 해결한다.

📝 의사코드

1. 박스와, 크레인을 내림차순으로 정렬한다.
2. 박스가 빌때까지 3~4번을 반복한다.
3. 크레인을 순회하면서 자기자신이 선택 할 수 있는 최대의 무게를 선택하여 박스를 제거시킨다.
4. 시간을 증가시킨다.
5. 시간 값을 출력한다.

💻 코드

import sys
input = sys.stdin.readline

N = int(input()) # 크레인의 수

cranes = list(map(int, input().split()))
M = int(input()) # 박스의 수
boxs_weight = list(map(int, input().split()))

cranes.sort(reverse=True)
boxs_weight.sort(reverse=True)

if cranes[0] < boxs_weight[0]: # 가장 무거운 박스가 크레인이 나를수 있는 무게보다 무거운경우
    print(-1)
else:
    time = 0
    while boxs_weight:
        for crain in cranes:
            for weight in boxs_weight:
                if crain >= weight:
                    boxs_weight.remove(weight)
                    break
                    
        time += 1
        
    print(time)

🎯 피드백 및 개선사항

• 제가 풀은 문제는 M 값이 더 커진다면, 시간복잡도가 O(M^2) 임으로 기하급수적으로 증가할 것이다.
• 아래의 문제의 풀이는 이진탐색으로 문제를 해결한 이력이 있어 참고하였습니다.

❓다른사람은 어떻게 풀었을까?

• 최적화 문제를 결정문제로 바꾼다 → 시간
• mid 값은 최대나올 수 있는 시간 1과 m사이의 값으로 둔다. (최소 : 1초 최대 : m초)
• mid값을 기준으로, 박스를 순회하면서, 크레인으로 시간안에 옮길 수 있는지 확인한다.
• 크레인으로 시간안에 옮길 수 있다면, 시간을 더 줄여본다.
• 크레인으로 시간안에 옮길 수 없다면, 시간을 더 늘려본다.
• 크레인이 시간안에 옮길 수 있는지 확인하는 방법은, boxes[i] > cranes[i//t]로 t를 증가시켜보면서, 박스 값이 더 크다면, 크레인으로 옮길 수 없으므로 없다. 모두 다 확인했음에도, 크레인이 더 크다면 옮길 수 있다.

import sys
n = int(sys.stdin.readline())
cranes = sorted(map(int, sys.stdin.readline().split()), reverse=True)
m = int(sys.stdin.readline())
boxes = sorted(map(int, sys.stdin.readline().split()), reverse=True)
if cranes[0] < boxes[0]:
	print(-1)
	exit()
def test(t):
	if n*t < m:
		return False
	for i in range(t, m, t):
		if boxes[i] > cranes[i//t]:
			return False
	return True
def bs(fun, l, r):
	while l <= r:
		mid = (l+r)//2
		if fun(mid):
			ans = mid
			r = mid-1
		else:
			l = mid+1
	return ans
print(bs(test, 1, m))