백준 2003번 : 수들의 합 2

링크 : https://www.acmicpc.net/problem/2003

아 진짜 마음에 안든다. 계속 쉽게 생각하려고 하니까 for문을 많이 쓰게 되고, 자연스럽게 연산 시간은 늘어나고, 시간이 늘어나니 틀리고, 이게 계속되니까 답답하다.

이 알고리즘은 망했다. 한시간 붙잡고 있다가 결국 검색하여 배웠다.

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

int main(){
	int N, M, elem, right = 0, left = 0, answer = 0, sum = 0;
	cin >> N >> M;
	
	int arr[10000];
	for (int i = 0; i < N; i++) {
		cin >> elem;
		arr[i] = elem;
	}

	while(right < N && left <= N) {
		if (sum < M) {
			if (right >= N)
				break;
			sum += arr[left++];
		}
		else if (sum == M) {
			answer++;
			sum -= arr[right++];
		}
		else {
			sum -= arr[right++];
		}
	}
	cout << answer << endl;
	return 0;
}

two pointer(left, right)의 행동 영역은 다음과 같다.
1. sum 값이 M보다 작으면 right의 위치를 오른쪽으로 옮겨 sum 값을 증가시킨다.
2. sum 값이 M보다 크거나 같다면 left의 위치를 오른쪽으로 옮겨 sum 값을 감소시킨다.

left가 right을 역전할 수 있다. 다음을 확인해보자.

1. 4 2
   1 1 1 1 의 경우이다.

   [left, right의 위치]
   0, 0
   1, 0
   2, 0
   sum : 2
   2, 1
   3, 1
   sum : 2
   3, 2
   4, 2
   sum : 2
   4, 3
   answer : 3

2. 10 5
   1 2 3 4 2 5 3 1 1 2 의 경우이다.

   0, 0
   1, 0
   2, 0
   3, 0
   3, 1
   sum : 5
   3, 2
   4, 2
   4, 3
   5, 3
   5, 4
   6, 4
   6, 5
   sum : 5
   6, 6
   7, 6
   8, 6
   9, 6
   sum : 5
   9, 7
   10, 7
   answer : 3