백준 2003 : 수들의 합 2 (C++, 투포인터 알고리즘 기초)

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

2003번: 수들의 합 2

 

투포인터의 기초로 여겨지는 문제로 개념을 알아둘 겸 문제풀이를 진행했다.

투포인터에 대한 개념은 아래 블로그에 내가 이해한 방식과 비슷하게 써져 있어 링크를 걸어두겠다.

https://ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0

[Algorithm] Two Pointers, 투 포인터

 

#include <iostream>
using namespace std;
int N, M; //M : arr[start]~[end-1]까지의 합
int arr[10001];

int main() {
	int start = 0, end = 0;
	int count = 0, sum = 0;
	cin >> N >> M;

	for (int i = 0; i < N; i++) 	cin >> arr[i];
	
	// start 포인터가 arr[N-1] 인덱스까지 탐색하도록 반복문 수행
	while (start < N) {
		//구간합이 M보다 작고 end포인터가 마지막인덱스를 넘지 않는 경우
		if (sum < M && end < N) {
			// end포인터 증가 및 sum값 변경
			sum += arr[end];
			end++;
			
		}
		else {
			// 구간합과 M이 같다면 count 증가
			if (sum == M) count++;
			//start포인터 증가 및 sum값 변경
			sum -= arr[start];
			start++;
		}
	}

	cout << count << endl;
	return 0;
}

처음에는 sum을 arr[start]부터 arr[end]까지의 합으로 두고 풀었는데 그럴 경우 sum의 초기값을 arr[0]으로 초기화해야 해서 좀 더 알고리즘에 맞게 sum을 arr[start]부터 arr[end-1]까지의 합으로 바꿔 풀었다.