[BOJ] 짐 챙기는 숌 - 1817 (S5)

시간 제한	메모리 제한
2 초	128 MB

문제

숌은 짐을 챙겨서 박스에 넣으려고 한다. 책은 탑 모양으로 쌓여있다. 위에서부터 책을 차례대로 박스에 넣는다. 박스의 무게 제한이 정해져 있어서, 무게 제한을 초과하지 않으면서 최대한 책을 넣으려고 한다.

입력

첫째 줄에 책의 개수 N과 박스의 최대 무게 M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000)

둘째 줄에 N개의 책의 무게가 위에서부터 차례대로 주어진다. 책의 무게는 1000보다 작거나 같은 자연수이다.

출력

필요한 박스의 최소 개수를 출력한다.

풀이

그리디 알고리즘으로 해결하는 간단한 문제이다. 위에서부터 차례대로 책을 박스에 넣되, 무게 제한을 초과하면 새 박스를 사용한다.

코드

MAX_W = 1000
N, M = map(int, input().split())

if N != 0:
    books = list(map(int, input().split()))
    cnt = 1
    remain_w = M
    for book in books:
        # 더 넣을 수 없으면 포장
        if remain_w < book:
            cnt += 1
            remain_w = M
        remain_w -= book

    print(cnt)
else:
    print(0)

시간 복잡도

O(N)