[C++] 투 포인터 1) BOJ 2003 수들의 합2

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

2003번: 수들의 합 2

1차원 배열에서 연속된 부분 배열의 합이 M인 경우의 수를 찾는 문제이다.

for문을 이용하면 O(N^2)이나온다

 

1.C++

#include <iostream>

using namespace std;

int num[30000];
int N, M;

void Solve() {
	int start = 0;
	int end = 0;
	int sum = 0;
	int cnt = 0;

	while (true) {
		if (sum >= M) sum -= num[start++];
		else if (end > N - 1) break;
		//while(end < N) 하면 num[end] == M 인경우 안세짐
		else sum += num[end++];
	
		if (sum == M) {
			cnt++;
		}
	}
	cout << cnt << '\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> num[i];
	Solve();
	return 0;
}

Start 와 End 두 개의 포인터를 이용한다

Start = 0, End = 0 에서 시작한다

합이 M보다 작으면 End가 한 칸 씩 이동하면서 더한다

합이 M과 같아지는경우 cnt를 1 올리고

초과하는 경우 Start를 한 칸 이동한다(Sum에서 start+1번째 수를 뺀다)

 

주의해아할 점이

while문의 종료 조건이 end > N-1 인데

그렇다고 while (end < N)하면 

M = 100 [1, 1, 1, 1, 100] 과같이 맨 마지막 요소가 M인경우를 체크하지 못한다.

 

 

2. Python

 

 

 

 

 

 

투 포인터

백준 온라인 저지 투포인터 문제 목록 

2003 수들의 합2  나의 풀이

1644 소수의 연속합  나의 풀이

1806 부분합 나의 풀이

2143 두 배열의 합  나의 풀이

1728 구슬 굴리기 나의 풀이

2886 Expected Allowance 나의 풀이