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

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

2003번: 수들의 합 2

연속된 숫자들의 부분합이 M이 되는 경우를 구하는 문제이다.

for문으로 무작정 구현하면 시간초과가 나기 때문에, 두 포인터를 사용해서 효율성을 고려해야 하는 문제였다. 

(만약 주어진 숫자들이 자연수가 아니라면 두 포인터를 사용할 수 없다.)

 

Two Pointers 는 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘으로, 최악의 경우에도 start와 end가 둘 다 배열의 마지막으로 오는 경우로 O(2n)의 시간복잡도를 갖는다.

 

따라서, 시간복잡도는 O(n)이다. 

 

#include <iostream>
using namespace std;

int N, M;
int a[10001];
int cnt = 0;

int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> a[i];
	}

	int start = 0, end = 0,tmp=0;

	while (end<=N) { //start==end인경우 0이므로, 항상 start<end가 보장
		if (tmp == M) cnt++;

		if (tmp >= M) {
			tmp -= a[++start];
		}
			
		else tmp += a[++end];

	}
	cout << cnt << endl;
}