[BOJ] 2003 수들의 합 2

문제 링크

 

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

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

 

 

이 문제는 모든 경우의 수를 생각하면서 풀면 O(N^2)의 시간 복잡도가 나오게 된다(시작지점 0~N, 도착지점 0~N까지 움직이면서 경우의 수를 푸는 경우). 문제의 제한 시간이 0.5초이고 N이 최대 10000까지 나올 수 있으므로 이렇게 구하면 시간 제한에 걸릴 수 있다. 좀 더 시간 복잡도가 작은 방법이 필요하다.

 

 

수열의 처음 값을 가지고 있는 변수 sum을 생각해보자. i를 1부터 N까지 증가시키면서 sum에 A[i]의 값을 더한다. 더한 값이 M과 동일하다면 경우의 수를 1 늘려주고, M보다 크다면 sum 값이 M보다 작아질 때까지 가장 마지막에 더한 값부터 차례대로 sum에서 빼준다. i가 N이 될 때까지 이 과정을 반복하면 i부터 j까지의 합이 M이 되는 모든 경우의 수를 구할 수 있다.

 

 

전체 코드는 다음과 같다.

#include <iostream>
using namespace std;
int main() {
	int i, n, m, ret=0, prev=0;
	cin >> n >> m;
	int arr[10000] = { 0 };
	int sum = 0;
	for (i = 0; i < n; i++) {
		cin >> arr[i];
	}
	sum = arr[0];
	i = 0;
	while (i < n) {
		if (sum == m) {
			ret++;
			sum -= arr[prev++];
		}
		else if (sum > m) sum -= arr[prev++];
		else sum += arr[++i];
	}
	cout << ret << endl;
}