백준 2003번(Silver 4)

오늘 포스팅은 기초 알고리즘인 투 포인터를 이용한 간단한 백준문제를 풀어보겠습니다.

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

2003번: 수들의 합 2

#include <iostream>
#include <vector>

int main() {
	int N, M;
	std::cin >> N >> M;

	std::vector<int> tmp(N, 0);
	for (auto& itr : tmp) {
		int tp;
		std::cin >> tp;
		itr = std::move(tp);
	}
	int sum = 0, e = 0, s = 0, count = 0;
	while (s < N) {
		if (sum >= M) {
			sum -= tmp[s]; s++;
		}
		else {
			if (e < N) {
				sum += tmp[e];
				e++;
			}
			else break;
		}
		if (sum == M) count++;

	}
	std::cout << count;

	return 0;
}

받는 M이 자연수이고, 수열의 값들이 자연수일 때만 가능한 알고리즘입니다. 

간단히 전부 탐색한다면 O(N^2)의 복잡도를 가지지만, 

이 알고리즘을 사용하면 O(N)으로 복잡도를 줄일 수 있습니다.