[백준/C++] 2003번: 수들의 합 2

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

2003번: 수들의 합 2

• 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <cstring>
#include <string>
#include <cmath>
#include <limits.h>

using namespace std;

int arr[10000];
int main() {
	
	int n = 0;
	int m = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int left = 0;
	int right = 0;
	int sum = arr[0];
	int cnt = 0;
	while (right < n) {
		
		if (sum > m) {
			sum -= arr[left];
			left++;
		}
		else if (sum < m) {
			right++;
			sum += arr[right];
		}
		else if (sum == m) {
			cnt++;
			right++;
			sum += arr[right];
		}
	}
	cout << cnt << endl;
	return 0;
   
}

• 알고리즘 분류 : 투포인터
• 문제 해설

투포인터 개념을 익히기 위한 문제였다. 투포인터는 기본적으로 left와 right의 두 변수를 가진다. 

1. left와 right는 모두 증가하는 방향으로만 움직일 수 있다. 

2. left가 right를 넘어서면 안된다.

이 문제에서는 연속하는 부분 수열의 합이 입력에서 원하는 수인 경우의 수를 카운트하는 문제였다. left와 right를 0부터시작해서 현재 구한 sum보다 원하는 수가 크면 right를 증가시겨 부분수열을 늘리고 , 작으면 left를 증가시켜 부분수열을 줄인다. 같게 되면 그 수를 카운트하고 right를 증가시킨다.