백준 - 부분합 (1806) [C++]

이 문제는 투 포인터를 이용해서 풀었다.

 

배열의 최대 길이가 10만이므로, O(N log N) 이하의 알고리즘을 고안해야 한다.

 

투 포인터를 사용할 경우 최대 2번씩밖에 각 요소를 접근하지 않으므로, O(N) 시간이 걸려 시간 안에 맞출 수 있다.

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX 100000

int N, S;
int arr[MAX];

int input() {
	cin >> N >> S;

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

	return acc;
}

bool isBaseCase(const int acc) {
	if (acc < S) {
		cout << 0 << '\n';
		return true;
	}

	if (acc == S) {
		cout << N << '\n';
		return true;
	}

	return false;
}

int length(const int left, const int right) {
	return right - left + 1;
}

int solve() {
	int left = 0;
	int right = 0;
	int acc = arr[left];
	int result = N;

	while (left <= right && right < N) {
		if (left == right) {
			if (acc >= S) {
				return 1;
			}
			else {
				right++;
				if (right < N) {
					acc += arr[right];
				}
			}
		}
		else {
			if (acc >= S) {
				result = min(result, length(left, right));
				acc -= arr[left];
				left++;
			}
			else {
				right++;
				if (right < N) {
					acc += arr[right];
				}
			}
		}
	}

	return result;
}

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

	const int acc = input();

	if (isBaseCase(acc)) {
		return 0;
	}

	cout << solve() << '\n';

	return 0;
}