BOJ #1092

LEVEL :

Gold5

문제 요약 :

무게를 가진 m개의 box들을 최대 무게의 조건이 있는 n개의 크레인으로 동시에 1분에 하나씩 옮길 때 최소 시간은?

해결 방안1 :

최소의 값을 묻는 문제에서 정렬을 이용하는 것을 보고 그리디 알고리즘인 것을 알았다. 먼저 크레인과 박스 모두 무거운 순서대로 정렬을 한다.
그런 다음 박스를 하나씩 크레인에 분배하는 방법으로 문제를 풀어 나갔다.
즉 해당 박스를 옮길 수 있는 크레인들중에 현재 박스의 갯수가 가장 적은 크레인에 박스를 할당해줌으로서 최종적으로 최대의 갯수의 박스를 가진 크레인의 박스 개수만큼이 최종걸리는 최소 시간이다.
시간복잡도는 O(MN)이다. #해결방안2에 비교하였을 때 비슷한 접근 방법인데 확실히 차이나는 시간복잡도이다. 항상 어떻게 하면 더 효율적으로 풀 수 있을 지 고민하면서 문제를 풀어야 겠다..

Solution

import sys
input = sys.stdin.readline
if __name__ == "__main__" :
    n = int(input().strip())
    c = sorted(map(int,input().strip().split()),reverse=True)
    m = int(input().strip())
    boxes = sorted(map(int,input().strip().split()),reverse=True)
    if c[0] < boxes[0] :
        print(-1)
        sys.exit(0)
    count= [0]*n
    for box in boxes : 
        index = 0
        for i in range(n) :
             # count[index] > count[i] 이말은 c[i] >= box 이 조건을 만족 하는 것중 가장 box를 적게 가진 crane에 box를 주기위한 조건이다.
            if c[i] >= box and count[index] > count[i] :
                index = i
            elif c[i] < box :
                break
        count[index] += 1
    print(max(count))   

해결 방안2 :

문제를 해결 할 때 가장 먼저 떠오른 방법이고, pypy3로는 통과 했지만, python3는 시간 초과로 해결 하지 못한 풀이법이다.
단순하게 박스를 옮길 수 있는 크레인을 발견하면 박스 리스트에서 박스를 하나씩 없애면서 박스가 빈 리스트일 때 까지 돌리는 방법으로 시간 복잡도가 반복문 3중에 del까지 O(M^3*N)이나 된다...
N,M의 크기의 최대 조건이 크지 않아 해결가능했던 것 같다..

Solution

import sys
input = sys.stdin.readline
if __name__ == "__main__" :
    n = int(input().strip())
    c = sorted(map(int,input().strip().split()),reverse=True)
    m = int(input().strip())
    box = sorted(map(int,input().strip().split()),reverse=True)
    if c[0] < box[0] :
        print(-1)
        sys.exit(0)
        
    count = 0
    while box : 
        for i in range(len(c)) :
            for j in range(len(box)) : 
                if c[i] >= box[j] :
                    del box[j]
                    break
        count+=1
    print(count)