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

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

1806번: 부분합

1. 주의할 점

- 2중 For문을 이용하지 않도록 한다 -> TLE 발생

- 투 포인터를 이용한다(이분탐색과 원리는 얼추 비슷하다. 예외처리할게 좀 있다)

 

2. 구현

- 모든 원소를 Arr[] 배열에 담고, 시작인 부분합(Tot)의 초기값을 Arr[0], Lidx =0, Ridx=0으로 둔다

- While문이 종료되는 경우로는 왼쪽 포인터가 오른쪽 포인터를 넘어갈 경우, 왼쪽 포인터가 배열의 오른쪽 끝에 도달한 경우

- 만약 부분합이 Sum보다 크다면 Result의 값을 비교 후 갱신한다.

이후, Lidx가 Ridx보다 왼쪽에 있다면 Lidx를 오른쪽으로 1칸 옮겨서 부분합의 크기가 작아지도록 한다.

만약 Lidx와 Ridx가 같다면 Lidx가 Ridx를 넘어가면 While문이 도중에 종료되므로 Ridx의 값을 1 증가시켜야 한다. 

하지만 Ridx가 Num-1에 위치해 있다면? -> 배열의 마지막 원소를 가리키고 있었으므로 While문을 종료한다

즉, Ridx != Num-1 일때만 Ridx++하고, 새로 추가된 원소의 값 만큼 Tot에 추가한다

- 부분합이 Sum보다 작다면 좀 더 간편하다. 우선 부분합(Tot)의 크기를 늘려주기 위해 Ridx++해야한다

하지만 Ridx==Num-1이라면? Ridx는 고정하고 Lidx를 ++하는 방법이 있지만, 이 경우 어떻게 해도 부분합이 Sum보다 작게 나오므르 While문을 종료한다

즉, Ridx! = Num-1인 경우 Ridx++와 부분합의 크기를 증가시킨다

 

#include <iostream>
#include <algorithm>
using namespace std;
int result = 100001, num;
long long sum;
int arr[100000];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> num >> sum;
	for (int i = 0; i < num; i++)
		cin >> arr[i];
	long long tot = arr[0];
	int lidx = 0, ridx = 0;
	while (lidx <= ridx && lidx < num) {
		if (tot >= sum) {
			result = min(result, (ridx - lidx) + 1);
			if (lidx < ridx) {
				tot -= arr[lidx];
				lidx++;
			}
			else if (lidx == ridx) {
				if (ridx == num - 1) break;
				else {
					ridx++;
					tot += arr[ridx];
				}
			}
		}
		else {		//더 추가해야 하는 경우
			if (ridx == num - 1) 		//더 추가할 원소가 없는 경우
				break;
			else {			//더 추가할 원소가 있는 경우
				ridx++;
				tot += arr[ridx];
			}
		}
	}
	if (result == 100001) result = 0;
	cout << result;
	system("pause");
	return 0;
}