백준 1092 풀이

문제 링크

---

문제

문제

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

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

입력

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

출력

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

---

풀이

내가 푼 풀이

1. 크레인과 박스를 내림차순으로 정렬한다.
2. 크레인 최댓값이 박스 최솟값보다 작다면 -1 출력한다.
3. count를 0으로 초기화하고, 크레인를 순회하면서 옮길 수 있는 박스를 리스트에서 제거한다.
4. 박스가 빌 때까지 반복하고, count // len(crains) + 1 을 출력한다.

import sys
input = sys.stdin.readline

crain_num = int(input())
crains = sorted(list(map(int, input().split())), reverse=True)
box_num = int(input())
boxes = sorted(list(map(int, input().split())), reverse=True)

crains = crains[:box_num]

if crains[0] < boxes[-1]:
    print(-1)
else:
    count = 0
    while boxes:
        for box in boxes:
            if crains[count % len(crains)] >= box:
                boxes.remove(box)
                break
        count += 1
print(count//len(crains)+1)

근데..

😂 눈물을 머금고 지선생한테 조언을 구했다.

ㅠ

❓ 어떻게 풀까?

1. 크레인과 박스 리스트를 받은 수 내림차순으로 정렬한다.

cranes = [32, 28, 25, 23]
boxes = [32, 29, 24, 20, 18, 16, 10, 7, 5, 2]

2. 크레인 별 위치와 해당 박스가 옮겨졌는 지를 저장하는 리스트 선언한다.

 # 크기는 크레인 수와 동일
position = [0 ,0, 0, 0]

 # 크기는 박스 수와 동일
checked = [False, False, False, False, False, False, False, False, False, False]

3. for문으로 position에 옮긴 위치 할당

# 해당 예시에선 첫 사이클에 32, 24, 20, 18 옮길 수 있음.
# 옮긴 박스의 인덱스를 position에 저장하고, 옮긴 박스를 checked를 통해 표시

# 첫번째 싸이클
position = [0, 2, 3, 4]
checked = [True, False, True, True, False, False, False, False, False, False]

# 두번째 싸이클
position = [1, 5, 6, 7]
checked = [True, True, True, True, True, True, True, False, False, False]

4. 박스를 하나 옮길 때마다 count 변수를 +1 해줘서 count = len(boxes) 될 때 까지 반복
5. 한 싸이클이 돌 때마다 result 변수를 +1 해줘서 결과값으로 프린트

# 첫번째 싸이클
position = [0, 2, 3, 4]
checked = [True, False, True, True, False, False, False, False, False, False]
count = 4
result = 1

# 두번째 싸이클
position = [1, 5, 6, 7]
checked = [True, True, True, True, True, True, True, False, False, False]
count = 8
result = 2

# 세번째 싸이클에서 count = 10이 되기 때문에, 반복문 종료 후 result = 3 반환

1️⃣ 정보 입력 및 변수 초기화

import sys

N = int(sys.stdin.readline())
cranes = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
boxes = list(map(int, sys.stdin.readline().split()))

# 모든 박스를 옮길 수 없는 경우
if max(cranes) < max(boxes):
    print(-1)
    sys.exit()

# 각 크레인이 현재 옮겨야 하는 박스의 번호 (0부터 시작)
positions = [0] * N
checked = [False] * M

# 크레인과 박스를 내림차순 정렬
cranes.sort(reverse=True)
boxes.sort(reverse=True)

• 먼저, 주어진 입력에서 크레인과 박스의 정보를 받아온다.
• 모든 박스를 옮길 수 없는 경우, -1 출력 후 종료한다.
• 각 크레인이 현재 어느 박스를 옮겨야 하는지를 저장하기 위한 positions 리스트를 선언한다.
• 어떤 박스가 이미 옮겨졌는지를 확인하기 위한 checked 리스트를 선언한다.
• 크레인과 박스의 무게는 내림차순으로 정렬한다.

2️⃣ 체크 로직

result = 0
count = 0

while True:
    if count == len(boxes):  # 박스를 다 옮겼다면 종료
        break
    for i in range(N):  # 모든 크레인에 대하여 각각 처리
        while positions[i] < len(boxes):
            # 아직 안 옮긴 박스 중에서, 옮길 수 있는 박스를 만날 때까지 반복
            if not checked[positions[i]] and cranes[i] >= boxes[positions[i]]:
                checked[positions[i]] = True
                positions[i] += 1
                count += 1
                break
            positions[i] += 1
    result += 1

• 각 크레인에 대해서, 해당 크레인이 옮길 수 있는 가장 무거운 박스를 찾는다.
  • 만약 옮길 수 있는 박스를 찾았다면, 해당 박스를 옮긴 것으로 표시하고, 해당 크레인의 positions 값을 증가시킨다.
  • 이를 통해 다음에 이 크레인이 박스를 옮길 때는 이보다 무게가 작은 박스를 옮기도록 한다.

• 위 과정을 모든 박스가 옮겨질 때까지 반복한다.
  • 이 때 각 크레인은 동시에 움직이므로, 한 번의 시간 단위마다 모든 크레인이 각각 하나씩 박스를 옮기는 것으로 계산한다.

• 마지막으로, 모든 박스가 옮겨진 후에는 총 걸린 시간을 출력한다.
  • 이 시간은 처음에 초기화한 시간에 계속 더해진 값으로, 모든 박스를 옮기는 데 필요한 최소 시간을 나타낸니다.

---

소스코드

import sys

N = int(sys.stdin.readline())
cranes = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
boxes = list(map(int, sys.stdin.readline().split()))

# 모든 박스를 옮길 수 없는 경우
if max(cranes) < max(boxes):
    print(-1)
    sys.exit()

# 각 크레인이 현재 옮겨야 하는 박스의 번호 (0부터 시작)
positions = [0] * N
checked = [False] * M

# 크레인과 박스를 내림차순 정렬
cranes.sort(reverse=True)
boxes.sort(reverse=True)

result = 0
count = 0

while True:
    if count == len(boxes):  # 박스를 다 옮겼다면 종료
        break
    for i in range(N):  # 모든 크레인에 대하여 각각 처리
        while positions[i] < len(boxes):
            # 아직 안 옮긴 박스 중에서, 옮길 수 있는 박스를 만날 때까지 반복
            if not checked[positions[i]] and cranes[i] >= boxes[positions[i]]:
                checked[positions[i]] = True
                positions[i] += 1
                count += 1
                break
            positions[i] += 1
    result += 1

print(result)

---

어렵다