c++ 백준_1806_"부분합"

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

1806번: 부분합

투포인터 (?) 방식으로 하였다.

​

left right 지점을 잡아 사용하였다.

​

처음

left = 0 에 두고

길이를 +1 하며

right 로 이동하며 값을 더한다.

​

현재 계속 더한 값이 S 이상이 되면

right를 그 위치에 고정시키고,

left를 right 방향으로 이동하고

길이를 -1시키며

현재 값에서 left 위치에 저장된 값을 뺀다.

​

그러면서 현재 값이 S 이상이 되면

최소 거리로 저장한다.

​

​

**

거리 안나오는 경우는 "0"으로 처리하랬으니 까먹지말자.

한번 틀..

 

#include <iostream>
using namespace std;

#define INF 1000000001
int arr[100001];

int main(void) {

	int N, S;

	cin >> N >> S;

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	int left = 0, right = 0;

	int sum = 0;
	int len = 1;

	int minimum = INF;
	sum = arr[left];
	while (left <= right && right < N) {

		if (sum >= S) {
			if (minimum > len)
				minimum = len;
			while (left < right) {
				sum -= arr[left];
				left++;

				len--;
				if (sum >= S) {
					if (minimum > len) 
						minimum = len;
				}
				else
					break;
			}
		}

		sum += arr[++right];
		len++;
	}

	if (minimum == INF)
		cout << "0";
	else
		cout << minimum;

}

​