백준 1806번 C++

백준 1806번 부분합

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

1806번: 부분합

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;
int arr[100005];
int n, m;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int x = 0; x < n; x++)
		cin >> arr[x];
	int en = 0, sum = arr[0];
	int ans = 987654321;
	for (int st = 0; st < n; st++) {
		while (en < n && sum < m) {
			en++;
			if (en != n)
				sum += arr[en];
		}
		if (en == n)
			break;
		ans = min(ans, en - st + 1);
		sum -= arr[st];
	}
    if(ans==987654321)
        ans=0;
	cout << ans;
}

문제 풀이

투 포인터를 이용해서 풀 수 있는 문제입니다.
투 포인터는 여기를 클릭하시면 알 수 있습니다.
코드 자체는 매우 간단합니다. n개만큼의 for문을
돌려주고 그 안에서 while문을 돌려줍니다.
이 반복문의 조건은 en값이 n보다 작고 sum값이 m보다 작아야 합니다. 그리고 sum값의 초기값은 배열의 첫 번째 값으로 설정합니다. while문을 돌리면서 n이 en이 아니라면 sum값에 arr[en]값을 더해줍니다. while문을 벗어나면 en==n일때의 경우를 고려해야 합니다. en과 n이 같다면 주어진 수열로 m값을 만들지 못했다는 뜻이기 때문에 for문을 종료시킵니다.
이 경우가 아니라면, 최소길이값을 ans값에 저장하고 sum에서 atr[st]를 빼줍니다. 맨 첫번째 원소부터  마지막  원소까지 차례대로 부분합을 구하는 개념입니다.