10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
출력
첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.
예제 입력 1
10 15 5 1 3 5 10 7 4 9 2 8 |
예제 출력 1
2 |
Solution
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
int N, S, min=100000, *arr=NULL, left=0, right=0;
scanf("%d%d", &N, &S);
arr=(int *)calloc(N+1,sizeof(int));
for(int n=1;n<=N;n++)
{
scanf("%d", &arr[n]);
arr[n]+=arr[n-1];
}
if(arr[N]<S)
{
printf("0\n");
return 0;
}
while(right<N && arr[++right]<S);
while(left<right && arr[right]-arr[++left]>=S);
min=right-left<min?right-left:min;
while(++right<=N)
{
while(left<right && arr[right]-arr[++left]>=S);
min=right-left<min?right-left:min;
}
printf("%d\n", min+1);
free(arr);
return 0;
}
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 17214번: 다항 함수의 적분 (0) | 2023.02.16 |
---|---|
<백준 알고리즘> 16935번: 배열 돌리기 3 (0) | 2023.02.16 |
<백준 알고리즘> 16927번: 배열 돌리기 2 (0) | 2023.02.14 |
<백준 알고리즘> 1068번: 트리 (0) | 2023.02.14 |
<백준 알고리즘> 1715번: 카드 정렬하기 (0) | 2023.02.14 |