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

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

1806번: 부분합

 

투 포인터와 누적 합 문제다.

 

주어진 배열에서 연속된 수들의 부분합 중에 s이상이 되는 수열 중, 가장 짧은 것의 길이를 구하는 문제다.

 

투 포인터를 사용하여 앞에서부터 포인터를 옮겨주며 해당 포인터들 사이의 누적 합 연산을 수행했다.

 

합이 s 미만이면 right 포인터를 한 칸 옮겨주어 합을 늘렸다.

right 포인터가 끝에 다달았다면 반복문을 종료했다.

(누적 합이 더 커질 수 없으므로)

 

합이 s 이상이면 left 포인터를 한 칸 옮겨주어 합을 줄였다.

합을 줄여도 s 이상일 수 있기 때문이다.

left 포인터를 옮기기 전에 left와 right 포인터가 같은 위치에 있는지 확인했다.

합이 s 이상이면서 길이가 1인 경우는 더 이상 최적의 답이 나올 수 없기 때문이다.

res를 갱신시키는 연산도 수행했다.

 

res 값은 최댓값으로 초기화 해둔 뒤 min() 연산을 수행했고

s 이상인 부분 수열이 없으면 0을 출력하도록 했다.

 

#include <iostream>
using namespace std;

int n, s, res = 1000000;
int arr[100000];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	cout.tie(0);
	
	cin >> n >> s;
	for (int i = 0; i < n; i++) cin >> arr[i];

	int left = 0, right = 0;
	int sum = arr[0];

	while (left < n) {
		if (sum < s) {
			right++;
			sum += arr[right];
			if (right >= n) break;
		}
		else {
			if (left == right) {
				cout << 1;
				return 0;
			}
			res = min(res, (right - left + 1));
			sum -= arr[left];
			left++;
		}
	}
	if (res == 1000000) cout << 0;
	else cout << res;
}