[ 백준 2003 ] 수들의 합 2

 

https://www.acmicpc.net/problem/2003

 

 

풀이 

이중루프로 i, j 탐색을 하면 N이 10^5이기 때문에 시간초과에 걸린다. 

그래서 누적합 또는 투포인터로 풀면 통과할 수 있다. 

 

 

1) 누적합 (prefix sum)

누적합으로 풀 수는 있는데 N이 더 컸더라면 누적합으로는 풀 수 없다. 

long[] pre = new long[N+1];
st = new StringTokenizer(br.readLine());
for(int i = 1 ; i <= N ; i++) {
    pre[i] = Long.parseLong(st.nextToken()) + pre[i-1];
}

int count = 0;
for(int i = 1 ; i <= N ; i++) {
    for(int j = 1 ; j <= i ; j++) {
        long sub = pre[i] - pre[j-1];
        if(sub == M) {
            count++;
        }
    }
}

System.out.println(count);

 

 

 

2) 투 포인터 

int[] arr = new int[N + 2];
st = new StringTokenizer(br.readLine());
for(int i = 1 ; i <= N ; i++) {
    arr[i] = Integer.parseInt(st.nextToken());
}

int l = 0;
int r = 1;
int count = 0;
long sum = arr[r];
while(r <= N) {
    if(sum < M) {
        r++;
        sum += arr[r];
    } else {

        if(sum == M) {
            count++;
        }

        l++;
        sum -= arr[l];
    }
}

System.out.println(count);