BOJ 2003

수들의 합 2

문제출처

몇몇 코딩테스트에서 투포인터 알고리즘을 전혀 알지 못해서 못푼 전적이 있어, 이 기회에 이 알고리즘을 배워보고자 이 기본 문제를 풀기로 했습니다.

문제 해석

N개의 수열의 i번째수부터 j번째수까지의 합이 M이 되는 경우의 수를 구하는 문제입니다.

설계(10)

kks227님의 블로그를 통해서 투포인터 알고리즘의 개념을 익혔습니다.

생각보다 너무나 간단한 알고리즘입니다.

기본적으로 s와 e의 두개의 변수로 인덱스를 차례대로 지나면서 원하는 결과를 찾는 기법입니다.

이 두개의 포인터를 사용하는 기법이기 때문에 투포인터라고 불린다고 합니다.

이 문제에서는 만약 sum(초기값 0)이 M보다 큰경우, e를 증가시키면서 해당 인덱스의 값을 더해줍니다.

반대로 sum이 M보다 작거나 같은 경우, s를 증가시키면서 해당 인덱스의 값을 빼줍니다.

이 방법으로 [s,e)의 구간합을 단 O(N+N)=O(N)의 시간복잡도만으로 구현할 수 있습니다.

구현(10)

코드

#include <iostream>
using namespace std;
#define MAXN 10000
int arr[MAXN];

int s,e,sum;
int N,M,ans;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    for (int i =0 ; i <N; i++){
        cin >> arr[i];
    }
    while (s<N|| e <N){
        if (sum<M){
            sum += arr[e++];
        }
        else{
            if (sum == M) ans++;
            sum -= arr[s++];
        }
    }
    cout << ans<<"\n";
    return 0;
}

디버깅

제출결과

0 ms

마무리

투포인터알고리즘을 이용하는 대표적인 문제였습니다.

이런 간단한 알고리즘을 알지 못해서 문제들을 못풀었으니.. 게으른 제 탓입니다.