[Python] 백준 1092 - 배 문제 풀이

Overview

BOJ 1092번 배 Python 문제 풀이
분류: Greedy (그리디)

---

문제 페이지

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

---

풀이 코드

from sys import stdin


def main():
    def input() -> str:
        return stdin.readline().rstrip()

    n = int(input())
    cranes = sorted(list(map(int, input().split())), reverse=True)
    m = int(input())
    boxes = sorted(list(map(int, input().split())), reverse=True)

    if boxes[0] > cranes[0]:
        print(-1)
        return

    time, cnt = 0, 0
    visit = [False] * m
    loc = [0] * n
    while cnt < m:
        time += 1
        for i in range(len(cranes)):
            while loc[i] < m and (visit[loc[i]] or boxes[loc[i]] > cranes[i]):
                loc[i] += 1

            if loc[i] < m:
                visit[loc[i]] = True
                loc[i] += 1
                cnt += 1

    print(time)


if __name__ == "__main__":
    main()

매 타임마다 크레인으로 옮길 수 있는 박스 중에서 가장 무거운 박스를 선택한다.
loc는 각 크레인이 마지막으로 옮긴 박스 위치를 저장하는 리스트이다. 매 타임마디 각 크레인은 해당 위치부터 옮길 박스를 탐색한다.