주행 거리 맞추기
문제
한 사람이 N일 동안 자전거를 타고 달린 거리를 날짜 순으로 적어 두었다. 1일차부터 N일차까지의 각 날에 달린 거리는 모두 자연수로 적혀 있다. 하루도 쉬지 않았으므로 거리가 0인 날은 없다.
이 사람은 기록을 들여다보다가, 연달아 이어진 며칠 동안 달린 거리의 합이 정확히 M이 되는 구간이 몇 군데인지 알아보고 싶어졌다. 여기서 연달아 이어진 구간이란 i일차부터 j일차까지처럼 날짜가 끊기지 않고 붙어 있는 구간을 말한다. 하루만 놓고 보는 구간도 구간으로 센다. 또한 시작한 날짜나 끝난 날짜가 다르면 서로 다른 구간으로 센다.
주행 기록과 목표 거리 M이 주어졌을 때, 연달아 이어진 며칠의 거리 합이 정확히 M이 되는 구간의 개수를 계산하는 프로그램을 작성하여라.
예를 들어 N=10일 동안의 주행 기록이 다음의 표와 같고, M=5라고 해보자.
| 날짜 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 달린 거리 | 1 | 2 | 3 | 4 | 2 | 5 | 3 | 1 | 1 | 2 |
거리 합이 정확히 5가 되는 구간을 모두 찾아 정리하면 다음의 표와 같다.
| 구간 | 1번 | 2번 | 3번 |
|---|---|---|---|
| 기간 | 2일차부터 3일차까지 | 6일차 하루 | 7일차부터 9일차까지 |
| 더한 거리 | 2와 3 | 5 | 3과 1과 1 |
| 거리 합 | 5 | 5 | 5 |
1일차에서 시작하는 구간을 하나씩 늘려 보면 1, 1+2=3, 1+2+3=6이 되어 5를 지나쳐 버린다. 달린 거리가 모두 1 이상이므로, 구간을 더 늘리면 합은 커지기만 한다. 그래서 합이 M을 넘어간 뒤에는 그 시작 날짜를 더 볼 필요가 없다. 시작 날짜를 하루 미루고 다시 보면 된다. 시작 날짜를 1일차부터 N일차까지 한 칸씩 미루면서 그때마다 끝 날짜를 필요한 만큼만 뒤로 옮기면, 모든 구간을 한 번씩 살펴본 것과 같은 결과를 얻는다. 따라서 이 경우의 정답은 3이다.
입출력 예시
예시 1
입력
10 5 1 2 3 4 2 5 3 1 1 2
출력
3
예시 2
입력
3 7 5 3 4
출력
1
예시 3
입력
5 2 7 7 1 7 4
출력
0
입력 조건
가장 먼저 첫째 줄에 기록한 날의 수 N과 목표 거리 M이 공백으로 구분되어 주어진다. N은 1 이상 10,000 이하의 자연수다. M은 1 이상 300,000,000 이하의 자연수다.
이어서 둘째 줄에 1일차부터 N일차까지 달린 거리가 공백으로 구분되어 한 줄에 주어진다. 각 날에 달린 거리는 1 이상 30,000 이하의 자연수다.
입력 전체의 크기는 최대 약 56KB다. 한 줄에 수가 최대 1만 개 들어오므로, 입력을 줄 단위로 읽어서 공백으로 나누는 방식으로 처리해야 한다.
출력 조건
거리 합이 정확히 M이 되는 구간의 개수를 첫째 줄에 출력한다. 그런 구간이 하나도 없으면 0을 출력한다.
요구사항
- 구간은 날짜가 끊기지 않고 이어진 구간만 셉니다
- 하루만으로 이루어진 구간도 구간으로 셉니다
- 시작한 날짜나 끝난 날짜가 다르면 서로 다른 구간으로 셉니다
- 날마다 달린 거리는 모두 1 이상입니다
- M이 N일 전체의 거리 합보다 크면 정답은 0입니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
3 7 5 3 4
1
5 2 7 7 1 7 4
0
10 5 1 2 3 4 2 5 3 1 1 2
3
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.