[C언어] 백준 1806 : 부분합

백준 1806 : 부분합

 

문제 링크:

www.acmicpc.net/problem/1806

1806번: 부분합

 

 

문제 내용:

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

 

 

Idea:

가장 짧은 길이를 구하기 위해 두 개의 포인터를 사용한다.

• left : 부분합의 가장 왼쪽 인덱스를 가리키는 용도
• right : 부분합의 가장 오른쪽 인덱스를 가리키는 용도

 

left와 right 모두 처음엔 첫 인덱스를 가리키게 하고 조건에 맞게 left와 right를 움직이며 최소 length를 찾도록 한다.

• 부분합이 S보다 작은 경우 : right를 한 칸 오른쪽으로 옮기고 해당 인덱스를 더해준다.
• 부분합이 S보다 크거나 같은 경우 : 문제의 조건을 충족하였으므로 length를 비교하여 기록하고 가장 왼쪽의 인덱스를 빼준다.

 

 

Code:

#include <stdio.h>
#define MIN(x,y) x<y?x:y
 
int arr[100000];
 
int main() {
    int N, S;
    scanf("%d %d", &N, &S);
    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);
 
    int sum = arr[0];
    int left, right, length = N + 1;
    left = right = 0;
 
    while (left <= right && right < N) {
        //합이 S보다 작으면 다음 인덱스의 값과 더해준다.
        if (sum < S) {
            sum += arr[++right];
        }
        //합이 S보다 크거나 같으면
        //length의 길이를 저장하고 제일 왼쪽의 인덱스를 빼준다.
        else{
            length = MIN(length, right - left + 1);
            sum -= arr[left++];
        }
    }
 
    if (length == N + 1) printf("0\n");
    else printf("%d\n", length);
    return 0;
}