BOJ 2003 (수들의 합 2)

• 문제
  N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.
  
  
• 입력
  첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
  
  
• 출력
  첫째 줄에 경우의 수를 출력한다.

#include<iostream>

using namespace std;
int N, M;
int arr[10001];
void fast_io()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

int main()
{
	fast_io();
	cin >> N >> M;
	int sum = 0; int cnt = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	int start = 0; int end = 0;
	while (end <= N)
	{
		if (sum < M)
		{
			sum += arr[end];
			end++;
		}
		else
		{
			if (sum == M)
			{
				cnt++;
				sum += arr[end];
				end++;
			}
			else
			{
				sum -= arr[start];
				start++;
			}
		}
	}
	cout << cnt;
	return 0;
}

    구간의 합을 물어보는 문제이다. 입력의 크기가 10000이고 제한 시간이 0.5초로 주어져 2중 반복문을 사용하면 시간 초과가 발생할 것으로 생각된다. 그래서 두 포인터 기법을 사용 (시작, 끝 index를 위한 변수 필요)
현재까지의 합이 원하는 합보다 작으면 현재 숫자를 더하고 end 포인터의 위치를 한 칸 뒤로 밀고 현재의 위치보다 크다면 start 위치의 값을 빼주고 한 칸 뒤로 밀어버린다.

원하는 타겟 값이 나온다면 횟수를 1늘리고 다음 수를 더해주면 된다.

시간 복잡도 : O(N)