CodeDrive

문제:

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N (10<=N<=100,000)과 S (0<S<=100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력:

첫째 줄에 구호고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

풀이방법:

시작과 끝을 나타내는 두 포인터를 통해서 연속된 부분합을 구하도록 한다. 두 포인터들은 다음 두 규칙에 따라 움직인다.

1. 두 포인터 사이의 합이 S를 넘지 않는다면 end 포인터를 이동시켜서 연속된 수의 길이를 늘린다.

2. 두 포인터 사이의 합이 S를 넘었다면(이상이라면), 현재 길이가 최소인지 확인한다. 그리고 start 포인터를 늘려서 연속된 수의 길이를 줄인다.

3. 1,2의 행동을 end가 수열의 길이를 초과하거나, start가 end 포인터를 넘어갈 떄까지 반복한다.

위 규칙을 마치고 난 다음에 초기 answer 값이 변하지 않았다면 조건을 만족하는 부분합을 찾지 못한 것이기 때문에 0을 출력하고, 아니면 정답을 출력하면 된다.

<2022-02-05> 재채점으로 인한 수정

부분합이지만 하나의 값으로만 S를 넘은 case가 존재한다.

10 10

10 1 1 1 1 1 1 1 1 1

ans 1

문제링크:

www.acmicpc.net/problem/1806