[2일차] 시간복잡도 A - 2003: 수들의 합 2

실버 Ⅲ

 

#include <iostream>

int arr[10000] = { 0, };

int main() {
	int N, M;
	scanf("%d%d", &N, &M);

	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}

	int sum = 0;
	int low = 0;
	int high = 0;
	int ans = 0;
	while (high <= N) {
		if (sum == M) {
			ans++;
			sum += arr[high];
			high++;
		}
		else if (sum < M) {
			sum += arr[high];
			high++;
		}
		else {
			sum -= arr[low];
			low++;
		}
	}
	printf("%d", ans);
}

처음 푼 투 포인터 문제

 

① 구간의 무언가를 구하는...(ex - 부분합)

② 그리고 그 구간이 유동적으로 변하는... (구간의 값이 바뀐다는게 아니라 구간 자체가 바뀌는)

(구간의 값이 자주 바뀌는거는 세그먼트 트리를 쓰는게 나음)

 

그런 문제에 쓰기 좋은 알고리즘이다

 

++추가++

if (sum == M) {
ans++;
sum += arr[high++];
} 

이 부분에서, sum += arr[high++];를 하든 sum -= arr[low++] 를 하든 아무 상관 없다