[백준 1806] 부분합

https://www.acmicpc.net/problem/1806

1806번: 부분합

 

연속된 수열에서 주어진 조건과 일치하는 부분합의 최소 길이를 찾는 문제이다.

 

연속된 수열에서 부분합을 찾아야 하기 때문에 투포인터를 사용해야 한다.

 

이 문제는 시작점이 동일하면서 같은 방향으로 움직이는 투포인터 유형이 되겠다.

 

L,R 두 포인터를 두고

L~R까지의 합이

1. 목표값인 S보다 작은 경우 R++

2. 목표값인 S보다 큰 경우 L++

을 한다.

 

L>R이 되면 합이 음수가 되고 그러면 무조건 목표값보다 작아지기 때문에

기본적으로 L<=R을 전제하고 있다.

따라서 R만 배열 길이를 넘지 않는 것을 while문 조건으로 걸어도 된다.

 

#include <stdio.h>
#include <algorithm>

using namespace std;
const int MAX = 100000;
int arr[MAX];
int main(void)
{
  int n;
  long long s;
  scanf("%d%lld", &n, &s);
  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }

  int l = 0, r = 0;
  long long sum = arr[0];
  int result = MAX + 1;
  while (r < n)
  {
    if (sum < s)
    {
      sum += arr[++r];
    }
    else
    {
      result = min(result, r - l + 1);
      sum -= arr[l++];
    }
  }

  if (result == MAX + 1)
  {
    result = 0;
  }
  printf("%d", result);
  return 0;
}