[알고리즘 - Python] BOJ 7450

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

7450번: Bin Packing

 

코드)

def func() -> int:
    cnt = 0     # bin의 개수    
    
    l = 0
    r = n - 1       # 뒤에서 찾아야함

    while l <= r:
        if item[l] + item[r] <= L:
            r -= 1
        l += 1
        cnt += 1

    return cnt
            
            
if __name__ == "__main__":
    n = int(input())        # 물건 개수
    L = int(input())        # bin의 길이
    item = [int(input()) for _ in range(n)]     # 아이템의 길이

    item.sort(reverse=True)     # 아이템을 내림차순으로 정렬

    bin_cnt = func()

    print(bin_cnt)

 

왜 최댓값 + 최솟값을 해야하는지 의아했는데,

L에 앞의 큰 숫자들을 빼버리면

남은 공간들은 또 다시 오름차순으로 정렬이 되기 때문에,

다시 최솟값으로 탐욕법을 적용해야 한다.