BOJ 2003 - 수들의 합 2 / C++

문제 링크 : https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

문제 풀이

투 포인터 알고리즘을 사용한다. 두 포인터는 모두 인덱스 0에서 시작한다.

 

목표는 m을 만드는 것이므로 합이 m보다 작다면 끝 포인터(en)을 늘려나가며 sum에 더해나간다.

 

만약 합이 m보다 크다면 앞 포인터(st)의 수를 뺀다. 이 때, 앞 포인터가 끝 포인터보다 커진다면 그 지점에 두 포인터를 위치시키고 다시 더해나간다.

 

만약 합이 정확히 m이 되면 정답 카운트를 증가시켜준다.

 

소스 코드

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int n, m;
    vector<int> v;
    cin >> n >> m;

    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }

    int st = 0, en = 0, sum = v[0], cnt = 0;

    while(st <= en && en < n){
        if(sum < m){
            sum += v[++en];
        }
        else if(sum == m){
            cnt++;
            sum += v[++en];
        }
        else { //sum이 m보다 클 때
            sum -= v[st++];

            if(st > en){
                en = st;
                sum = v[st];
            }
        }
    }

    cout << cnt;
}