[백준]1806_부분합

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

Solved

✔ 이중포문으로 풀 시 O(N^2)
✔ 기본적인 투 포인터 문제: 시간복잡도 O(N) 공간 복잡도 O(1)

• 포인터 2개가 같은 방향으로 진행하는 경우: [백준]2003, 카카오 인턴쉽2020: 보석 쇼핑
• 포인터 2개가 양 끝에서 반대 방향으로 진행하는 경우: [백준]2470

투 포인터 알고리즘은 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 해를 구하는 방법이다.

정렬된 리스트를 두 개의 포인터를 이용해 순차적으로 접근하면서 두 포인터 구간의 값이 타겟 값과 같을 때까지 포인터를 조작하는 기법.

1. 리스트를 오름차순으로 정렬한다.

2. 포인터 left는 리스트의 시작점을, 포인터 right는 리스트의 끝점을 가리킨다.

3. left와 right가 만날 때까지(즉, 모든 경우를 확인할 때까지) 다음을 반복한다.

   3-1. A[left]와 A[right]의 합이 타겟 값(S)과 같다면 조건을 만족하므로 출력하고, left를 1 증가, right를 1 감소시킨다.

   3-2. A[left]와 A[right]의 합이 타겟 값(S)보다 작다면 left를 1 증가시킨다.

   3-3. A[left]와 A[right]의 합이 타겟 값(S)보다 크다면 right를 1 감소시킨다.

using namespace std;
#include <iostream>
#define MAX 100000

int arr[MAX];

int main() {
	int n, s;
	cin >> n >> s;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	int start = 0, end = 0, answer = 0x3f3f3f3f;
	int sum = 0;
	while (end <= n) {
		if (sum >= s) {
			answer = min(answer, end-start);
			sum -= arr[start++];
		}
		else if (sum < s) sum += arr[end++];
	}
	if (answer == 0x3f3f3f3f) answer = 0;
	cout << answer << '\n';