[BOJ_2003][Two_Pointers]수들의 합 2

완전탐색 대신 투포인터 (two pointers) 알고리즘 활용

 

입력:

N: 데이터 수 

M: 구간의 합과 비교해볼 값

ㅁㅁㅁㅁㅁ: N개의 데이터

---

각 'ㅁ' 마다 데이터가 들어오는 칸이라고 생각하면, 들어온 값들의 합이 M과 일치할 수 있는 '경우의 수'를 구해야 합니다. 

ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ

위 예시와 같이 밑줄친 곳과 중앙선이 그어진 곳 모두 합이 M과 일치할 수 있습니다. 

 

시간복잡도를 낮추기 위해 두 개의 포인터를 활용해 front 와 back의 위치에 대해 알고 있도록 합니다. 주의할 점은, 합이 M 보다 클 때 front에 해당하는 값을 한 번 지워서는 M과 일치할 수도 있는 합을 놓칠수도 있다는 것입니다. 이 부분은 테스트케이스에 나와있지 않아 틀리기 쉽습니다. 

#include <iostream>

/* 수들의 합 2 */ 
using namespace std;

int n, m, arr[10001];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("../../input.txt", "r", stdin);
    
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }

    int ans = 0;
    int sum = 0;
    for(int front = 0, back = 0; back < n; back++){
        // cout << front << ":" << back << endl;
        sum += arr[back];
        while(sum > m) {
            sum = sum - arr[front];
            front++;
        }
        if(sum == m){
            ans++;
            sum = sum - arr[front];
            front++;
        }
    }

    cout << ans;
}