납품 기간
문제
한 공장이 N일 동안 날마다 만들어 낸 부품의 수를 날짜 순으로 적어 두었다. 1일차부터 N일차까지의 각 날에 만든 부품의 수는 모두 자연수이며, 하나도 만들지 못한 날은 없다.
공장은 주문받은 부품 S개를 한 번에 납품해야 한다. 다만 창고 사정 때문에, 연달아 이어진 며칠 동안 만든 부품만 한 묶음으로 실어 보낼 수 있다. 다시 말해 i일차부터 j일차까지처럼 날짜가 끊기지 않고 붙어 있는 기간을 골라, 그 기간에 만든 부품을 모두 실어야 한다. 실어 보내는 부품의 수가 S보다 많아도 괜찮다.
공장장은 창고를 되도록 짧게 쓰고 싶어서, 주문량을 채우는 기간 가운데 날의 수가 가장 적은 것을 고르려고 한다.
생산 기록과 주문량 S가 주어졌을 때, 그 기간에 만든 부품의 수가 S 이상이 되는 연달아 이어진 기간 가운데 가장 짧은 기간의 날의 수를 계산하는 프로그램을 작성하여라.
예를 들어 N=10일 동안의 생산 기록이 다음의 표와 같고, S=15라고 해보자.
| 날짜 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 만든 부품 수 | 5 | 1 | 3 | 5 | 10 | 7 | 4 | 9 | 2 | 8 |
하루만 골라서는 15개를 채울 수 없다. 가장 많이 만든 날도 5일차의 10개뿐이다. 그러면 이틀을 묶는 경우를 보아야 한다. 이틀 묶음 가운데 몇 가지를 놓고 견주어 보면 다음의 표와 같다.
| 기간 | 4일차부터 5일차까지 | 5일차부터 6일차까지 | 7일차부터 8일차까지 |
|---|---|---|---|
| 만든 부품 수 | 5와 10 | 10과 7 | 4와 9 |
| 합계 | 15 | 17 | 13 |
| 주문량 충족 | 채움 | 채움 | 못 채움 |
4일차부터 5일차까지의 이틀을 묶으면 합계가 정확히 15가 되어 주문량을 채운다. 5일차부터 6일차까지를 묶어도 17개로 채운다. 하루로는 채울 수 없고 이틀로는 채울 수 있으므로, 이 경우의 정답은 2다.
입출력 예시
예시 1
입력
10 15 5 1 3 5 10 7 4 9 2 8
출력
2
예시 2
입력
3 852 430 2107 3679
출력
1
예시 3
입력
5 2126 3139 1433 4375 6042 5320
출력
1
입력 조건
가장 먼저 첫째 줄에 기록한 날의 수 N과 주문량 S가 공백으로 구분되어 주어진다. N은 1 이상 100,000 이하의 자연수다. S는 1 이상 1,000,000,000 이하의 자연수다.
이어서 둘째 줄에 1일차부터 N일차까지 만든 부품의 수가 공백으로 구분되어 한 줄에 주어진다. 각 날에 만든 부품의 수는 1 이상 10,000 이하의 자연수다.
입력 전체의 크기는 최대 약 0.5MB다. 한 줄에 수가 최대 10만 개 들어오므로, 입력을 줄 단위로 읽어서 공백으로 나누는 방식으로 처리해야 한다.
출력 조건
그 기간에 만든 부품의 수가 S 이상이 되는 가장 짧은 기간의 날의 수를 첫째 줄에 출력한다. N일 전체를 다 묶어도 S를 채울 수 없는 경우에는 0을 출력한다.
요구사항
- 기간은 날짜가 끊기지 않고 이어진 기간만 고를 수 있습니다
- 실어 보내는 부품의 수가 S보다 많아도 됩니다. S 이상이면 됩니다
- 하루만으로 이루어진 기간도 고를 수 있습니다
- 날마다 만든 부품의 수는 모두 1 이상입니다
- N일 전체를 다 묶어도 S를 채울 수 없으면 0을 출력합니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
3 852 430 2107 3679
1
5 2126 3139 1433 4375 6042 5320
1
10 15 5 1 3 5 10 7 4 9 2 8
2
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.