[baekjoon 1806] 부분합 (투 포인터) (C++)

www.acmicpc.net/problem/1806

1806번: 부분합

시간제한이 0.5초로 매우 짧기 때문에, 부분합을 구하기 위해서 2중 for문을 돌면서 풀면 풀리겠지만 시간은 O(N^2)로 시간제한에 걸리게 된다.

 

따라서 이 문제는 O(N)의 시간 복잡도로 풀이가 가능한 두 포인터를 이용해야 한다.

 

두 포인터란 배열을 가리키는 포인터 인덱스 l, r (왼쪽, 오른쪽 맘대로)를 선언 후, 매번 조건과 비교하면서 왼쪽, 오른쪽 인덱스를 바꿔주며 배열을 탐색하는 것이다.

 

0. 배열의 원소는 모두 자연수여야 한다.

1. 시작은 L, R포인터 모두 0에 두고, 탐색을 시작한다.

2. 현재 합이 조건에 맞지 않으면 오른쪽 포인터를 한 칸 옮겨주어 인덱스 1번을 탐색한다.

3. 계속 탐색하다가 조건에 맞으면 왼쪽 인덱스를 한 칸 옮겨주면서 구간을 좁혀준다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int arr[100001], n, s, sum, cnt, l, r;

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

	int result = 100001;

	while (1) {
		if (sum < s) {
			if (r == n) {
				break;
			}
			sum += arr[r];
			r++;
		}
		else {
			result = min(result, r - l);
			sum -= arr[l];
			l++;
		}
	}

	if (result == 100001) {
		cout << 0;
	}
	else
		cout << result;
}

1. r == n 조건

오른쪽 포인터가 배열의 크기와 같다는 것은 이미 끝까지 탐색했다는 것이다(크기가 n이면 배열은 0~n-1)

그러므로 while문을 종료해준다.

 + 아닌 경우 오른쪽 포인터를 옮겨주면서 합을 늘려준다. (아직 조건보다 합이 작기 때문에)

 

2. 합보다 큰 경우 일단 결과를 저장해주고, 왼쪽 포인터를 한 칸 옮겨주면서 합을 줄여준다. (구간 길이의 최소를 구하는 것이기 때문)