[백준 2003번] 수들의 합 2

[백준 2003번] 수들의 합 2

www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

 

 문제

 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

 

 입력

 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

 

 

 출력

 첫째 줄에 경우의 수를 출력한다.

 

 

 풀이

#include <iostream>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N,M;
	cin >> N >> M;
	
	vector<int> temp;
	for(int i=0;i<N;i++){
		int a;
		cin >> a;
		temp.push_back(a);
	}
	
	int left=0, right=0;
	int cnt = 0;
	int sum = 0;
	while(right <= N){
		if(sum < M){
			sum += temp[right++];
		}
		else if(sum > M){
			sum -= temp[left++];
		}
		else{
			cnt++;
			sum += temp[right++];
		}
	}
	cout << cnt;
	return 0;
}

 처음에는 1644번을 풀어보려고 하다가 투 포인터에 대한 개념을 알고자 이 문제를 풀어보았다. 투포인터를 모른다면 아마 나처럼 구간 합을 응용해서 풀고자 할 것이다. 하지만 O(1)로 구간 합을 구하더라고 M이 되는 경우의 수를 구하는 과정에서 O(N^2)의 큰 시간이 소모된다. 따라서 구간 합으로 푸는 것은 적절하지 않고 투 포인터를 사용해야 한다. 투포인터는 시간 복잡도가 무려 O(1) 밖에 되지 않는다.

 투 포인터는 배열에서 다른 원소를 가리키는 2개의 포인터를 이용하여 원하는 값을 계산하는 방식으로 left, right 두개의 포인터로 문제를 풀었다. 투 포인터에 대한 자세한 설명은 m.blog.naver.com/kks227/220795165570 에 있다.