Subsequence (부분합) 1806번 [백준]

부분합 문제로 point to point 개념을 사용하여 쉽게 풀어내었다.

2003번 문제와 매우 비슷한 유형이다.

 

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, j) for(int i=0;i<j;i++)
typedef long long ll;

const int inf = 987654321;

int main() {
	fast_io;
	int n, s;
	cin >> n >> s;
	vector<int> v(n);
	for (int& x : v)cin >> x;
	int low = 0, high = 0;
	int sum = v[0];
	int length = inf;
	while (low <= high && high < n) {
		if (sum > s) {
			length = min(length, high - low + 1);
			sum -= v[low++];
			if (low > high && low < n)
			{
				high = low;
				sum = v[low];
			}
		}
		else if (sum == s) {
			length = min(length, high - low + 1);
			if (high == n - 1)break;
			sum += v[++high];
		}
		else {
			if (high == n - 1)break;
			sum += v[++high];
		}
	}
	if (length == inf)cout << 0 << endl;
	else cout << length << endl;
	return 0;
}

2003번: 수들의 합 2