백준 s4 2003 수들의 합 2 c++

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

2003번: 수들의 합 2

 

문제

길이가 N인 수열이 주어질 때, A[i] ~ A[j]의 합이 M인 경우의 수 구하기

 

풀이

그냥 이중 for문으로 풀면 10^8이라 시간 초과가 날 수도 있음 .. 

투 포인터로 O(N)으로 구할 수 있다

 

수도 코드

// en범위를 넘으면, sum에 더할 수 있는 건 다 더했는데도 M은 못 넘은 거 이므로 끝내는 게 맞음
while: st < N && en < N
	if sum == M
    	ans++
        st 한 칸 옮기고 sum -=
    else if sum < M
    	en 한 칸 옮기고 sum +=
	else if sum > M
    	st 한 칸 옮겨서 합 줄이기 sum -=

 

 

전체 코드

/*boj s4 2003 수들의 합 2*/
#include <iostream>
#define MAXN 10005
using namespace std;

int N, M;
int arr[MAXN];
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;

    for (int i = 0; i < N; i++)
        cin >> arr[i];

    int st = 0;
    int en = 0;
    int sum = arr[st];

    int ans = 0;
    while (st < N && en < N) {
        if (sum == M) {
            ans++;
            sum -= arr[st];
            st++;
        } else if (sum < M) {
            en++;
            sum += arr[en];
        } else { // sum > M
            sum -= arr[st];
            st++;
        }
    }

    cout << ans << "\n";
}