[백준] 1806번: 부분합

문제

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

설명

누적 합을 저장하는 두 개의 배열을 사용한다. 특정 지점의 인덱스를 i라고 할 때, sum1은 인덱스가 0부터 i까지의 누적 합을 저장하며 sum2는 i부터 n-1까지의 누적 합을 저장한다.

 

그 다음, 투 포인터를 통해 조건에 맞는 구간을 찾는다. tot-sum1[l]-sum2[r]은 구간 (l, r)의 누적 합이다.

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n, m;
	cin >> n >> m;

	// (전체 합) - (0부터 i까지의 합) - (j부터 n-1까지의 합) = m
	int tot = 0;
	vector<int> sum1, sum2;
	sum1.push_back(0);
	for (int i = 0;i < n;i++) {
		int x;
		cin >> x;
		tot += x;

		sum1.push_back(sum1[i] + x);
	}

	for (int i = 0;i < n;i++) {
		sum2.push_back(tot - sum1[i]);
	}
	sum2.push_back(0);

	int l = 0, r = 0;
	int ans = 100000001;
	while (1) {
		if (tot - sum1[l] - sum2[r] < m) {
			r++;
			if (r > n)
				break;
		}
		else if (tot - sum1[l] - sum2[r] >= m) {
			if (r - l < ans)
				ans = r - l;

			l++;
		}
	}

	if (ans == 100000001)
		cout << 0;
	else
		cout << ans;
}