백준 2003번 수들의 합 2

< 백준 2003번 수들의 합 2 - 마포 코딩박 >

사용한 알고리즘: 투포인터


 N개의 수로 된 수열이 주어지고, 이 수열의 i~j 수들의 합이 M이 되는 개수를 찾는 문제입니다. 저는 투포인터를 써서 해결했습니다.

문제풀이는 다음과 같습니다.
(1) (코드: arr[11111])
 수열을 받을 배열을 넉넉히 잡아 각 수열의 수들을 저장했습니다.

(2) (코드: 15~33)
 s이상 e미만의 수열의 합 sum = arr[s]+arr[s+1]+...+arr[e-1] 라 두고,
 1. sum == M 인 경우 ans++ , sum+=arr[e] , e++
 2. sum < M 인 경우 sum+=arr[e], e++
 3. sum > M 인 경우 sum-=arr[s], s++
 4. e>N 인 경우 끝
 의 과정으로 계산해주었습니다.

	#include <iostream>
	#include <algorithm>
	using namespace std;
	int N, M;
	int arr[11111];
	int sum, ans, s, e;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	cin >> arr[i];
	// s: 시작, e: 끝 (s 이상 e 미만 )
	while(s<=e){
	// 답
	if(sum == M){
	ans++;
	sum+=arr[e];
	e++;
	}
	else if(sum>M){
	sum -= arr[s];
	s++;
	}
	// sum < M 인 경우
	else{
	sum += arr[e];
	e++;
	}
	// 끝까지 봤으면 끝 (arr[0~N-1], arr[N]은 없다)
	if(e>N) break;
	}
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 2003.cpp hosted with ❤ by GitHub