[알고리즘] - BOJ #1092 배

• 이번 문제는 BOJ #1092, 배입니다. 문제 명세 및 입출력 예시는 링크를 참고해주세요!

접근 방식

해당 문제에서는 최대 50개의 크레인과 그 무게, 그리고 최대 100만개의 상자들과 그 무게가 주어집니다. 그리고 크레인으로 박스를 모두 옮기는데 필요한 최소 횟수를 구해야 합니다.

따라서 크레인으로 한 번 옮길 때 가능한 최대 갯수의 박스를 옮겨야 하고, 이를 위해서는 크레인들을 돌면서 해당 크레인이 들 수 있는 최대 무게의 박스를 옮겨야 합니다.

알고리즘 자체는 크게 복잡해 보이지 않았습니다. 크레인 리스트와 박스 리스트를 크기가 큰 순서대로 정렬한 뒤, 크레인들을 순회하며 박스들의 무게와 크레인의 무게를 비교하여 들 수 있는 최대 무게의 박스를 들도록 합니다.

min_trans = 0
while(box):
    min_trans += 1

    for cr in crane:
        for i in range(len(box)):
            if cr >= box[i]:
                box.pop(i)
                break

이러한 로직을 코드로 작성한 바는 위와 같습니다.

그러나 이 경우, 최악의 경우 M * N * M의 복잡도를 갖게됩니다.

M의 최댓값이 1,000,000이고 N의 최댓값이 50이기 때문에, 최대 50억번의 연산을 수행하게 됩니다. 당연히 2초라는 시간 제한 내에서는 돌아갈 수 없습니다. (일반적으로 10억번의 연산을 수행하는데 1초 넘짓한 시간이 필요하다고 하니, 5초 넘짓한 시간이 주어져야 실행이 가능하지 않을까 싶습니다.)

해결 방식

이러한 시간 복잡도 문제를 해결하기 위해, 크레인이 정렬되어 있다는 점을 활용했습니다. 크레인을 순회하는 과정에서, 해당 순번의 크레인이 들지 못한 박스는, 당연하게도 뒷 순번의 크레인 또한 들 수 없다는 점을 활용했습니다.

즉, 위의 코드에서 현재 돌고 있는 크레인인 cr과 i번째 박스인 box[i]와의 비교에서 박스가 더 무겁다는 결과가 나왔다면, 다음 순번의 크레인은 i번째의 박스와는 비교할 필요가 없게 됩니다.

이를 구현하기 위해서 save_point라는 변수를 추가하여, 크레인이 돌면서 박스를 어디까지 순회했는지 체크했습니다. 그리고 다음 순번의 크레인이 순회할 때는 save_point 이후의 박스만 순회하도록 했습니다.

 min_trans = 0
 while(box):
    min_trans += 1

    # O(N+M)
    save_point = 0
    for cr in crane:
        for i in range(save_point, len(box)):
            save_point = i
            if cr >= box[i]:
                box.pop(i)
                break

위의 로직을 코드로 작성한 바는 위와 같습니다.

이 결과, 크레인을 모두 순회하는 과정에서 박스 또한 한 번만 순회하게 됨으로, O(N*M)의 시간 복잡도를 O(N+M)으로 낮출 수 있었습니다.

Lesson

해당 문제는 그리디 알고리즘으로 분류됩니다. 알고리즘 상으로는 해당 크레인이 들 수 있는 최대 무게의 박스를 옮기면, 최종적으로 문제의 해에 도달할 수 있기 때문에 그리디 알고리즘에 포함된다고 생각했습니다. 또한 시간 복잡도를 줄이는 과정에서도, 그리디한 방식으로 접근하고 있음을 인식하고 앞서 비교한 상자의 경우 추가로 비교가 필요 없다는 점을 활용하여 문제를 해결할 수 있었습니다.

문제 바로가기 👉BOJ #1092