[C] 백준 2003번 수들의 합

두 개의 포인터를 활용하여 수열의 부분합을 구해보자.

게시 2024/07/12

완전 탐색으로도 풀 수 있지만 투 포인터를 활용하면 더욱 빠르게 풀 수 있다.

작성자 HEINZ

조회 3 분 소요

Problem

$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을 넘지 않는 자연수이다.
출력: 첫째 줄에 경우의 수를 출력한다.

Solve

1. 내 풀이 (완전 탐색)

  
#include <stdio.h>

int main(void) {
    int n, m, cnt = 0;
    scanf("%d %d", &n, &m);
    int A[n];
    for (int i = 0; i < n; i++) scanf("%d", &A[i]);
    for (int i = 0; i < n; i++) {
        int sum = A[i];
        for (int j = i; j < n && sum <= m; sum += A[++j]) {
            if (sum == m) cnt++;
        }
    }
    printf("%d", cnt);
    return 0;
}

2. 투 포인터

사후적 풀이 필자는 이 풀이를 생각하지 못했다.

$i$일 때 $M$보다 크거나 같은 최소 $j$의 값을 $J(i) \geq M$라고 하자.

$A[x]$의 값은 자연수이므로 $J(i + 1) \geq J(i)$이다.

이때 $A[x] \neq 0$이므로 $i$부터 $J(i)$까지의 합을 조사하면 된다.

즉 실제 조사하는 구간의 수는 $N$개이다.

한편 $i$와 $j$는 감소하지 않는다.

즉 반복문은 최대 $2N$번 실행된다.

시간복잡도가 $\mathcal{O}(N^2)$에서 $\mathcal{O}(N)$로 준 것이다!

  
#include <stdio.h>

int main(void) {
    int n, m, cnt = 0;
    scanf("%d %d", &n, &m);
    int A[n];
    for (int i = 0; i < n; i++) scanf("%d", &A[i]);
    for (int i = 0, j = 0, sum = 0; i < n; sum -= A[i++]) {
        while (j < n && sum < m) sum += A[j++];
        if (sum == m) cnt++;
    }
    printf("%d", cnt);
    return 0;
}