[백준 / BOJ] 2003번 : 수들의 합2

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

2003번: 수들의 합 2

 

이전에 올렸던 [소수의 연속합]이라는 문제에서 투 포인터를 구현했을 때 if문과 break을 남발한 것이 마음에 걸려 같은 알고리즘의 문제를 풀어보았다.

 

골자는 똑같다. 구간합이 주어진 수 M과 같거나 큰 경우에는 start를 1 올리고, M보다 작은 경우에는 end를 1 올려 주어서 해당하는 arr의 값을 더해준다. M과 같은 경우에는 count도 1 더해주어야 한다.

	while(start <= end) {
			if(sum < M) {
				sum += arr[end++];
			} else if(sum == M) {
				cnt++;
				sum -= arr[start++];
			} else {
				sum -= arr[start++];
			}
		}

이렇게 구현하면, sum += arr[end++]에서 ArrayIndexOutOfBoundsException이 날 수 밖에 없다. 따라서 다음과 같이 변경해주었다. 마지막으로 end를 올려준 다음에는 sum과 M을 비교할 수가 없으니, while문 밖에서 한 번 더 검사해주도록 했다.

		while(start <= end) {
			if(sum < M) {
				sum += arr[end++];
                if(end == N) break;
			} else if(sum == M) {
				cnt++;
				sum -= arr[start++];
			} else {
				sum -= arr[start++];
			}
		}
        
        if(sum == M) cnt++;

 

하지만 여전히 부족하다. 만일 end가 N이 되어 while문 밖으로 나왔는데, 그 때의 sum 값이 M보다 크다면? start를 올려가면서 값을 줄여볼 수가 없기 때문에 이런 경우 정답을 낼 수 없다. 따라서 다음과 같이 변경하였다.

		while(start <= end) {
			if(sum < M) {
            	if(end == N) break;
				sum += arr[end++];
			} else if(sum == M) {
				cnt++;
				sum -= arr[start++];
			} else {
				sum -= arr[start++];
			}
		}

 end를 올린 직후 검사하는 것이 아니라, 올리기 직전에 검사하는 것이다. 이 경우, while문 밖에서 또다시 조건 검사를 할 필요도 없다.

 

전체 코드는 다음과 같다.

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		long M = Long.parseLong(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			int n = Integer.parseInt(st.nextToken());
			arr[i] = n;
		}
		
		int start = 0;
		int end = 1;
		long sum = arr[start];
		int cnt = 0;
		
		while(start <= end) {
			if(sum < M) {
                if(end == N) break;
				sum += arr[end++];
			} else if(sum == M) {
				cnt++;
				sum -= arr[start++];
			} else {
				sum -= arr[start++];
			}
		}
		
		System.out.println(cnt);
	}

}