백준 2003번 수들의 합 2 (C++)

 

알고리즘 공부 2주차: 투포인터

투포인터에 대해 잘 모른다면 이전에 정리해 둔 개념 정리를 한번 읽어보고 오는 것을 추천합니다. 

알고리즘 공부 2주차: 투포인터 개념

알공 2주차: 투포인터 개념

백준 2003번 수들의 합 2

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

12919번: A와 B 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을 넘지 않는 자연수이다.

출력

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

예제 보려면 더보기 클릭

예제 입력 1

4 2
1 1 1 1

예제 출력 1

3

예제 입력 2 

10 5
1 2 3 4 2 5 3 1 1 2

예제 출력 2

3

---

문제 설명

특정 구간에서 수들의 합이 M이 되는 경우의 수를 찾는 문제이다. 

이걸 반복문을 통해 하나하나 더해가며 일일이 구할 경우 시간초과가 걸린다. 

따라서 투포인터를 사용해 모든 경우의 수를 하나하나 따져가는 것이 방법이다. 

바로 예시로 들어가보면 배열의 크기 n=4, m=2일때 우리는 더해서 2가 되는 경우의 수를 구해야한다. 

예제 설명 1

front와 back 모두 0번째 인덱스에서 시작한다. 

여기서 0부터 0까지 더한 값은 1이므로 m보다 작다. 

따라서 back을 1 더해준다. 

예제 설명2

0부터 1까지 더한 값이 2, m과 같으므로 카운트 개수를 세준다. 

또한 같을때에도 back을 1 더해준다. 

 

예제 설명3

sum>m이므로 front를 1 더해준다. 

이때 더하기 전에 미리 sum에서 front번째 값을 빼주는 게 좋다. 

sum-=arr[f] ; 

예제 설명4

똑같이 sum과 m이 같으므로 카운트 개수를 늘려준다. 

앞으론 위 과정을 반복한다. 

예제 설명5

예제 설명6

예제 설명7

front와 back 모두 더이상 늘어날 수 없는 배열에 끝에 도달했으므로 종료한다. 

투 포인터 코드를 짤때 주의해야할 점은 f와 b가 주어졌을때 f에서 b까지의 값을 일일이 더하는 것이 아니다. 

f와 b가 늘어나는 상황에 따라 그때그때 더하거나 빼주는 것이다. 

int b=0, f=0;
int sum = arr[0];//첫번째 값을 미리 주고
while(b<n){
	if(sum <= m){
    	b++; //b가 늘어날 경우
        sum += arr[b]; //sum에도 늘려줌
    }
    else{
    	sum -= arr[f];//f를 늘리기전 미리 빼주고
        f++;//f 늘어남
    }
}

위 코드는 예시를 위해 새로짠 코드이므로 밑에 정답코드랑은 다릅니다. 코드를 수정하여 제출해야합니다. 

또한 b가 n과 같아졌을때는 배열의 끝에 도달했다는 것이므로 종료해줘야 한다. 

 

---

제출한 코드 (C++)

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
vector <int> v[1005];
using ll = long long int;
ll a[10005];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n, m;
	cin >> n >> m;
	for (ll i = 0; i < n; i++) {
		cin >> a[i];
	}
	ll f = 0, b = 0;//앞뒤
	int cnt = 0;
	int sum = a[f];
	while (b < n) {
		if (sum == m) {
			cnt++; b++;
			sum += a[b];
			if (b == n) break;
		}
		else if (sum<= m) {
			b++;
			sum += a[b];
			if (b == n) break;
		}
		else {
            		sum -= a[f];
			f++;
			
		}
	}

	cout << cnt;

}