[Beakjoon] 백준 1817번 Python

Beakjoon 1817, 짐 챙기는 숌
solved.ac Silver5
Greedy 알고리즘

문제

숌은 짐을 챙겨서 겨울캠프에서 집으로 가려고 한다. 근데 숌은 공부를 많이 하러 캠프에 온 것이기 때문에 책을 엄청나게 많이 가지고 왔다. 숌은 이 책을 방에 탑처럼 쌓아 놨다.

숌은 책을 박스에 차곡차곡 넣어서 택배로 미리 보내려고 한다. 책은 탑처럼 차곡차곡 쌓여있기 때문에, 차례대로 박스에 넣을 수밖에 없다.

각각의 책은 무게가 있다. 그리고 박스는 최대 넣을수 있는 무게가 있다. 숌이 필요한 박스의 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 책의 개수 N과 박스에 넣을 수 있는 최대 무게 M이 주어진다. N은 0보다 크거나 같고 50보다 작거나 같은 정수이고, M은 1,000보다 작거나 같은 자연수이다. N이 0보다 큰 경우 둘째 줄에 책의 무게가 공백을 사이에 두고 주어진다. 책의 무게는 M보다 작거나 같은 자연수이다.

출력

첫째 줄에 필요한 박스의 개수의 최솟값을 출력한다.

Solution

N, M = map(int, input().split())
if N != 0 :
    data = list(map(int, input().split()))
    weigth = 0
    result = 1
    for i in range(N-1, -1, -1) :
        weigth += data[i]
        if weigth > M :
            result += 1
            weigth = data[i]
    print(result)
else :
    print(0)

풀이

먼저 짐의 개수가 0개인 경우 0을 출력하기 때문에 미리 처리를 해둡니다.

책이 차곡차곡 쌓여 있기 때문에 반복문을 역방향으로 수행합니다. 확인중인 책을 현재 박스에 담아 그 무게를 박스에 더해줍니다.

책을 더했을 때의 박스 무게가 입력받은 M 보다 더 커지게 되면 박스를 하나 추가하고 그 박스에 방금의 책을 담아줍니다. 그리고 그 박스에 다시 새로운 책들을 추가해줍니다.

그렇게 반복문이 종료될 때까지 반복합니다.

---

1817번: 짐 챙기는 숌