[백준/C++] 2003번: 수들의 합 2

문제 링크

---

아이디어

설명

투 포인터 알고리즘을 이용했다.
연속된 수들의 합이 m보다 작은 경우, end를 sum에 더하고 1 증가시키고
m보다 같거나 큰 경우, start를 sum에서 빼고 1 증가시켰다.

end는 더하기 담당, start는 빼기담당으로 생각한다.

코드 설명

처음에는 위 코드와 같이 end < n으로 돌려봤는데 예제코드1의 결과가 2가 나왔다.
이는 마지막에 1을 더해서 sum == m 이 나왔음에도 불구하고 코드 구조상 cnt++하지 못하고 바로 while문을 빠져나와서 생긴 문제였다.

그래서 end <= n로 바꾸고 배열 인덱스 범위 초과 오류를 방지하기 위해 end로 배열에 접근하는 코드 바로 윗줄에 if문으로 따로 처리하였다. 예제코드1과는 달리 마지막 숫자 하나를 더했는데 sum보다 작은 경우, sum += v[end++] 부분을 실행할 수 있기 때문이다.

---

제출코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;

	vector<int> v(n);

	for (int i = 0; i < n; i++) 
		cin >> v[i];

	long long sum = 0;
	int cnt = 0;

	int start = 0, end = 0;

	while (start <= end && end <= n)
	{
		if (sum < m)
		{
			if (end == n) 
            	break;
			sum += v[end++];
		}
		else if (sum >= m) // m보다 크다면 start를 sum에서 빼줌
		{
			if (sum == m)
				cnt++;
			sum -= v[start++];
		}
	}

	cout << cnt;

	return 0;
}