[백준] 2003

수들의 합 2

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

풀이

#include <iostream>

int main(void) {
    int n, m, left = 0, right = 0, cnt = 0, sum = 0;
    int arr[10001] = {0,};
    std::cin >> n >> m;

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

    while (left <= right && right <= n) {
        if (sum >= m) {
            if (sum == m) cnt++;
            sum -= arr[left++];
        } else if (sum < m) {
            sum += arr[right++];
        }
    }
    std::cout << cnt << "\n";
}

반성회

투 포인터 알고리즘이란?

• 하나의 배열에 두 개의 포인터 (위의 코드에서 left, right) 를 사용하여 문제를 푸는 알고리즘
• 단 한 번의 반복문 내에 포인터를 두 개 두고 수행하므로 시간복잡도가 O(N) 밖에 되지 않는다

1. left, right를 0으로 초기화, 이는 arr[1001] 의 인덱스로 사용된다
2. 합 (sum) 이 m보다 작으면 sum에 arr[right]를 더하고, right를 뒤로 한 칸 이동시킨다
3. 합이 m보다 크면 sum에서 arr[left] 를 빼고, left를 뒤로 한 칸 이동시킨디
4. 합이 m과 같으면 cnt를 1 증가시키고, sum 에서 arr[left] 를 빼고 left를 뒤로 한 칸 이동시킨다