[백준] 2003번 : 수들의 합 - 자바[Java]

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

2003번: 수들의 합 2

풀이

누적합 + 투포인터 알고리즘

 

먼저 arr[0] ~ arr[i] 까지 더한 값을 저장하는 누적합 배열 sumArr[i]를 생성한다.

sumArr[0] = 0

sumArr[i+1] = arr[0] ~ arr[i] 까지 더한 값

 

처음에는 이중 for문으로 모든 경우의 수를 구하려 했지만,

O(n^2) , N=100000 -> N^2 = 10억

시간제한은 0.5초이므로 시간초과가 날 수 있다.

 

따라서 O(N)으로 줄이기 위해 투 포인터 알고리즘을 사용하였다.

 

코드

import java.io.*;
import java.util.*;

public class Main {
	
	static int[] sumArr;
	static int n, m, cnt = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		sumArr = new int[n+1];
		
		int sum = 0;
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(st.nextToken());
			sumArr[i+1] = sum + num;
			sum += num;
		}
		
		find();
		
		System.out.println(cnt);
		
		br.close();
	}
	
	private static void find() {
		int i = 0;
		int j = 1;
		for (; i <= j && j <= n;) {
			int diff = sumArr[j] - sumArr[i];
			if (diff == m) {
				cnt++;
				j++;
			}
			else if (diff > m) {
				i++;
			}
			else {
				j++;
			}
		}
	}
}