1806번 : 부분합

2019/11/30 - [알고리즘 일기] - 2003번: 수들의 합 2

2003번: 수들의 합 2

의 맨 마지막 코드랑 비슷하게 풀면된다.

 

#include<iostream>
#include<vector>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, s;
	cin >> n >> s;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int R = 0;
	int L = 0;
	long long sum = a[0];
	int ans = 0;
	while (L <= R && R < n) {
		if (sum < s) { // 목표보다 작으면 R증가
			R++;
			if (R >= n) break;
			sum += a[R];
		}
		else if (sum == s) { // 같으면 R증가, ans 저장
			if (ans == 0 || ans > R - L + 1) {
				ans = R - L + 1;
			}

			R++;
			if (R >= n) break;
			sum += a[R];
		}
		else if (sum > s) { // 클경우 L 증가
			if (ans == 0 || ans > R - L + 1) {
				ans = R - L + 1;
			}

			sum -= a[L];
			L++;
			if (L > R) { // L이 R 보다 커질 경우 같이 증가
				R = L;
				sum = a[L];
			}
		}
	}
	cout << ans << '\n';
	return 0;
}