택배 차량의 순서대로 싣기

문제

택배 작업장에는 오늘 운반할 택배 상자 N개가 한 줄로 놓여 있다. 각 상자에는 무게가 적혀 있으며, 작업자는 줄의 앞에서부터 상자를 하나씩 확인한다. 사용할 수 있는 차량은 한 대이고, 차량에 동시에 실린 상자 무게의 합은 적재 한도 C를 넘을 수 없다. 모든 상자의 무게는 양의 정수이며, 각각의 상자는 빈 차량에 실을 수 있다. 작업을 시작할 때 차량은 비어 있다. 작업자는 다음 상자를 현재 차량에 실어도 적재 한도를 넘지 않으면 그 상자를 즉시 싣는다. 상자를 실은 뒤 무게의 합이 적재 한도와 정확히 같아지는 경우에도 정상적으로 실은 것으로 처리한다. 이때 뒤에 확인할 상자가 남아 있다면, 다음 상자를 확인하는 과정에서 출발 여부를 판단한다. 다음 상자를 실으면 적재 한도를 넘는 경우에는 현재 실린 상자들을 운반하기 위해 차량이 출발한다. 차량은 실린 상자들을 모두 내려놓고 빈 상태로 작업장에 돌아온다. 작업자는 방금 싣지 못했던 상자를 돌아온 차량에 먼저 싣고, 이어서 남은 상자를 같은 규칙으로 처리한다. 상자의 순서를 바꾸거나, 한 상자를 나누어 싣거나, 뒤쪽의 가벼운 상자를 먼저 고르는 일은 없다. 마지막 상자까지 확인한 뒤에도 차량에 상자가 남아 있다면 그 상자들을 운반하기 위해 한 번 더 출발한다. 빈 차량은 출발하지 않으며, 작업장으로 돌아오는 이동은 출발 횟수에 포함하지 않는다. 운반 거리와 이동 시간은 고려하지 않는다. 이 규칙은 작업 절차로 정해져 있으므로, 다른 적재 방법을 찾아 출발 횟수를 줄이는 것이 목적은 아니다. 주어진 순서와 규칙에 따라 모든 상자를 운반할 때 차량이 출발하는 총횟수를 구한다.

입력

첫째 줄에 상자 수 N과 차량의 적재 한도 C가 공백으로 구분되어 주어진다. N은 1 이상 1,000 이하의 정수이고, C는 1 이상 1,000 이하의 정수이다.
둘째 줄에 상자의 무게를 나타내는 정수 N개가 운반할 순서대로 주어진다. 각 무게는 1 이상 C 이하이다.

출력

모든 상자를 운반하기 위해 차량이 출발하는 총횟수를 정수 하나로 출력한다. 상자가 적어도 하나 있으므로 출력값은 항상 1 이상이다.

6 10
6 4 3 8 2 5

4

4 12
2 3 4 3

1

1 1
1

1

출처: Devin.KR 자체 제작