백준 1806번

백준 1806번 (부분합)

처음에는 연속된 수들이라는 의미를 잘못파악하여 꽤나 골치가 아팠었다. 난 연속된 수들이라는 의미가 1,2,3,4...이런 +1씩되는 수라고 생각하였다. 하지만 다시보니 그런 의미가 아니라 그냥 수열 내에서 순서가 연속적이라는 의미였다...ㅋㅋ

가장 먼저 떠오른 해결방안은 완전탐색을 돌리는 것이었다. 하지만 해당 문제의 시간제한은 0.5초... 무조건 시간초과일 것이다. N도 100000미만이기에 무조건이다...

이제 pair를 사용하여 index도 같이 저장하고 내림차순으로 해당 배열을 정렬한 뒤 pair의 index와 동시에 앞에부터 하나씩 점검하는 방식으로 해결을 하려했다. 하지만 해당 방식도 너무 복잡해보일뿐 아니라 구현해도 시간초과가 예상되었다...

결국은 이중포인터를 사용해서 해결하는 문제였다. 시작점과 끝점을 0으로 잡고 부분합을 배열의 첫번째 원소 값으로 초기화한다. 또한 현재 부분합 길이를 나타낼 len을 매우 큰 수로 잡아준다. 그리고 sum < s일 경우 끝점을 +1 해주고 sum에 끝점에 있는 원소를 더해주고, s==sum일 경우 현재 len과 끝점-시작점+1 중 더 작은 값으로 최신화해주고, 끝점을 +1해주고 sum에 끝점에 있는 원소를 더해준다. 마지막으로 sum > s인 경우 현재 len과 끝점-시작점+1 중 더 작은 값으로 최신화해주고, sum에서 현재 시작점에 있는 원소를 빼주고, 시작점에 +1을 해준다. 이것을 반복하여 해결할 수 있었다.

#include <bits/stdc++.h>

using namespace std;

int n, s;

int main() {
	scanf_s("%d %d", &n, &s);
	vector<int> v(n);

	for (int i = 0; i < n; i++) 
		scanf_s("%d", &v[i]);

	int l = 0;
	int r = 0;
	int sum = v[0];
	int len = 1e9;

	while (l <= r && r < n) {
		if (sum < s) {
			r++;
			if (r >= n)
				break;
			sum += v[r];
		}
		else if (sum == s) {
			len = min(len, r - l + 1);
			r++;
			if (r >= n)
				break;
			sum += v[r];
		}
		else {
			len = min(len, r - l + 1);
			sum -= v[l];
			l++;
		}
	}

	if (len == 1e9)
		printf("0");
	else
		printf("%d", len);

	return 0;
}