택배 묶음의 목표 무게

문제

한 택배 작업장에서는 작은 택배 상자들을 하나의 운반 묶음으로 모으고 있다. 작업대에는 N개의 상자가 도착한 순서대로 놓여 있으며, 직원은 앞에 놓인 상자부터 차례대로 묶음에 넣는다. 각 상자의 무게는 양의 정수이고, 작업 중에 상자의 순서를 바꾸거나 중간의 상자를 건너뛸 수 없다. 작업장에서는 묶음의 목표 무게를 K로 정했다. 직원은 상자를 하나 넣을 때마다 지금까지 넣은 모든 상자의 무게를 더해 확인한다. 누적 무게가 처음으로 K 이상이 되는 순간, 목표 무게를 채웠다는 표시를 남긴다. 목표 무게와 정확히 같아지는 경우뿐 아니라, 마지막에 넣은 상자 때문에 목표 무게를 넘어서는 경우에도 표시를 남긴다. 상자 하나를 나누어 일부만 넣는 일은 없다. 구하려는 값은 표시를 남기게 되는 상자의 번호이다. 상자 번호는 도착한 순서대로 1번부터 N번까지 매긴다. 따라서 첫 번째 상자 하나만으로 목표 무게를 채우면 답은 1이다. 여러 상자를 넣은 뒤 목표 무게를 채웠다면 그 순간 마지막으로 넣은 상자의 번호가 답이다. 묶음 자체나 포장재의 무게는 누적 무게에 포함하지 않는다. 모든 상자를 넣어도 누적 무게가 K보다 작으면 목표 무게를 채울 수 없으므로 답은 0으로 정한다. 반대로 한 번 목표 무게를 채운 뒤에는 뒤에 남은 상자들의 무게가 답에 영향을 주지 않는다. 입력에 적힌 상자들을 순서대로 처리했을 때, 목표 무게를 처음 채우는 상자의 번호를 구하는 프로그램을 작성한다.

입력

첫째 줄에 상자 수 N과 목표 무게 K가 공백으로 구분되어 주어진다. 둘째 줄에 1번부터 N번까지 상자의 무게 W₁, W₂, …, Wₙ이 공백으로 구분되어 주어진다. 모든 입력값은 정수이며, 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000, 1 ≤ Wᵢ ≤ 1,000이다. 모든 무게는 같은 단위를 사용한다.

출력

누적 무게가 처음으로 K 이상이 되는 상자의 번호를 정수 하나로 출력한다. 모든 상자를 넣어도 목표 무게를 채우지 못하면 0을 출력한다.

5 14
3 4 6 2 8

4

4 20
5 5 5 5

4

3 10
2 3 4

0

출처: Devin.KR 자체 제작