BOJ 2003 · 수들의 합 2

알고리즘 분류 : 투 포인터  

N개의 수로 구성된 수열에서 연속된 수의 합이 M이 되는 경우의 수를 구하는 문제다. 투 포인터 알고리즘으로 구현할 수 있다.

• 왼쪽과 오른쪽을 가리키는 포인터 Left, Right를 만든다. 이 포인터는 배열의 인덱스를 가리킨다.
• Left, Right는 각각 인덱스 0부터 시작한다.
• 1. 현재의 합(Sum)이 M 이상인 경우
• - Left가 가리키는 값을 합에서 빼고, Left를 1 증가시킨다.
• 2. 현재의 합이 M 미만인 경우
• - Right의 값이 인덱스 N인 경우, 루프를 종료한다. 즉, Right가 배열의 범위를 벗어난 경우에 종료한다.
• - Right가 N이 아니라면, Right가 가리키는 값을 합에 더하고, Right를 1 증가시킨다.
• 3. 현재의 합이 M인 경우
• - 정답(Answer)를 1 증가시킨다.
• 1 ~ 3 과정을 반복한다.
• 자세한 과정은 아래 그림을 참조. N = 7, M = 3, A = [1 2 3 4 3 2 1] 인 경우의 예시.

---

C++ 소스코드

#include <cstdio>

int n, m, ans, sum, left, right;
int a[10000];

void solve() {
    while (true) {
        if (sum >= m) {
            sum -= a[left];
            left++;
        } else {
            if (right == n) break;
            sum += a[right];
            right++;
        }
        if (sum == m) ans++;
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
    solve();
    printf("%d\n", ans);
    return 0;
}

---

Python 3 소스코드

n, m = map(int, input().split())
a = list(map(int, input().split()))

def solve():
    left = right = ans = s = 0
    while True:
        if s >= m:
            s -= a[left]
            left += 1
        else:
            if right == n:
                break
            s += a[right]
            right += 1
        if s == m:
            ans += 1
    return ans

print(solve())

---

참고

• 백준 온라인 저지 : BOJ 2003