[BOJ / C++] 수들의 합 2 (투포인터)

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

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> arr(n+1);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int en = 0;
    int cnt = 0;
    int sum = arr[0];
    for (int st = 0; st < n; st++) {
        while (en < n && sum < m) {
            en++;
            sum += arr[en];
        }
        if (en == n) break;
        if (sum == m) cnt++;
        sum -= arr[st];
    }
    cout << cnt;
}

 

 

2. 시간복잡도

st와 en이 최대 n 번이므로 시간복잡도는 O(2n)이다. 만약 brute force 식으로 3중 for 문을 돌면 n = 10^4 이므로 n^3 = 10^12 > 10^7으로 0.5초 제한 시간초과가 발생한다. prefix sum dp테이블을 미리 만들고 2중 for 문으로 해도 n^2 = 10^8 > 10^7으로 시간초과 위협이 있다.

따라서 투포인터를 이용해 O(n)에 해결하는 것이 좋다. 

 

 

3. 분석

sum > m이 되어버리면 더이상 sum == m일 가능성이 없는 것에 주목해야한다. sum < m일 때까지만 en을 증가시키면서 sum을 계산하고 sum == m인 경우에만 cnt를 증가시키는 방식으로 투포인터를 활용한다.