[알고리즘] C++ 백준 2003 수들의 합 2

백준 2003 

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

2003번: 수들의 합 2

풀이 전 나의 생각

N개의 수로 된 수열이 주어진다. 이 수열의 i번째 수부터 j번째 수까지의 합이

M이 되는 경우의 수를 구해야 한다.

 

조건

- N(1 ≤ N ≤ 10,000)

- M(1 ≤ M ≤ 300,000,000)

- A[x]는 30,000을 넘지 않는 자연수

 

과정

N, M, A[x]는 int의 범위를 벗어나지 않기 때문에 데이터 타입을 int로 설정해준다.

 

2중 for문만을 사용하여 합이 M이 되는 경우의 수를 구한다면 10000 * 10000의 계산 횟수가 시간 제한 0.5초를 맞추지 못하기 때문에투 포인터를 사용하여 문제를 해결해야 한다.

 

1. i번째 수부터 j번째 수까지의 누적합을 투 포인터로 구한다.

while (start <= end)
	{
		if (sum >= M)
		{
			if (sum == M) ans++;
			sum -= arr[start++];
		}
		else if (end == N)
		{
			break;
		}
		else
		{
			sum += arr[end++];
		}
	}

누적합이 M 이상이 될 때까지 end 포인터를 증가시켜준다.

 

현재 누적합이 M이상이 됐다면 M과 누적합의 값이 같은지 확인하고 결과값을 증가시켜준다.

다음으로 누적합이 M이상이라는 것은 더 이상 end 포인터를 증가시키며 합을 크게 만들 필요가

없다는 의미기 때문에 start 포인터를 증가시켜주며 이전에 더했던 start 포인터 위치의 값을 제거해준다.

 

이 과정을 반복하며 M과 누적합이 같아지는 경우의 수를 모두 구하면

문제에서 요구하는 답을 얻을 수 있다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

int arr[10001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int N, M;
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	int start = 0, end = 0, sum = 0, ans = 0;

	while (start <= end)
	{
		if (sum >= M)
		{
			if (sum == M) ans++;
			sum -= arr[start++];
		}
		else if (end == N)
		{
			break;
		}
		else
		{
			sum += arr[end++];
		}
	}

	cout << ans;
}