[백준 1806] 부분합 [C]

백준 - 1806

---

풀이

연속된 수들의 부분합이기 때문에 Two Pointers로 쉽게 구현할 수 있다.

 

start, end가 가르키는 배열의 합들이 S이상이면 최소 길이를 구해야 하며, 만약 sum이 S보다 작으면 end+1번째 요소를 더해주고, 그렇지 않다면 start번째 요소를 빼주는 방식으로 풀이했다.

---

소스코드

#include <stdio.h>
#define min(a, b) a < b ? a : b
int main(){
    int arr[100000], N, S, start = 0, end = 0;
    scanf("%d %d %d", &N, &S, &arr[0]);
    for (int i = 1; i < N; i++)
        scanf("%d", &arr[i]);	
	
    int cnt = 1e5, sum = arr[0];
    while (start <= end && end < N){
        if (sum >= S)
            cnt = min(cnt, end - start + 1); 
        sum += (sum < S ? arr[++end] : -arr[start++]);
    }
    printf("%d", cnt == 1e5 ? 0 : cnt);
}

---

출처

1806번: 부분합