[백준][C++] 1806: 부분합

문제 링크: https://www.acmicpc.net/problem/1806

 

투포인터로 푸는 문제입니다.

i=0, j=0부터 시작해서 [i, j] 구간의 합이 s 이상이면 j-i+1로 최소 길이를 업데이트하고, i를 1 늘립니다. 구간 합이 s 미만이면 j를 1 늘립니다.

 

구간의 합을 구할 때 반복문을 쓰면 시간초과가 나오겠죠? 그래서 첫 칸부터 i, j 이동에 따라 누적해줘야 합니다.

구간의 합이 s 이상이어서 i를 1 늘릴 때 i를 1 늘리기 전에 구간합에서 v[i]를 빼주고, 구간 합이 s 미만일 때 j를 1 늘린 뒤 v[j]를 구간합에 더해줍니다. 이때 j가 n이 되면 배열 범위를 벗어나는 것이니 예외처리를 해줘야 하고요

i, j를 늘리는 것과 v[i], v[j]를 구간 합에 빼거나 더하는 순서가 뒤바뀌면 안되겠죠?

 

설명을 좀 두리뭉실 하게 했는데;; 직접 그려보시면 바로 이해가 될겁니다

#include <bits/stdc++.h>
using namespace std;

const int INF = 987654321;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n, s;
	cin >> n >> s;
	vector<int> v(n);
	for (auto& c : v)
		cin >> c;

	int i = 0, j = 0;
	int sum = v[0];
	int min_len = INF;
	while (1) {
		if (sum >= s) {
			min_len = min(min_len, j - i + 1);

			sum -= v[i];
			++i;
		}
		else {
			++j;
			if (j == n) break;
			sum += v[j];
		}
	}

	cout << (min_len==INF ? 0 : min_len) << '\n';

	return 0;
}