[백준_2003번] 수들의 합 2

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

2003번: 수들의 합 2

[문제]

 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을 넘지 않는 자연수이다.

 

[코드]

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

public class BaekJoon_2003 {
	static int[] arr;
	static int n,m;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		n=Integer.valueOf(st.nextToken());
		m=Integer.valueOf(st.nextToken());
		
		st=new StringTokenizer(br.readLine());
		arr=new int[n];
		
		// 입력값 받기 
		for(int i=0;i<n;i++) {
			arr[i]=Integer.valueOf(st.nextToken());
		}
		
		System.out.println(twoPointer());
	}
	
	static int twoPointer() {
		int count=0;
		int startPoint=0,endPoint=0;
		int sum=0;
		
		while(true) {
			/*
			 * m보다 sum이 크면 값을 줄여서 m을 맞춰야 하므로 
			 * 현재 startpoint 값을 빼고 한칸 앞으로 이동한다. 
			 */
			if(sum>=m) 
				sum-=arr[startPoint++];
			
			// 범위를 초과할 경우 종료
			else if(endPoint>=arr.length) 
				break;
			
			/*
			 * m보다 sum이 작으면 값을 늘려서 m을 맞춰야 하므로 
			 * 현재 endpoint를 한칸 앞으로 이동시키고 그 인덱스의 원소 값을 더해준다.
			 */
			else 
				sum+=arr[endPoint++];
			
			if(sum==m) 
				count++;
		}
		
		return count;
	}
}

 

[고찰]

 이번 문제는 처음 접해보는 알고리즘인 투포인터를 사용해야 정답 처리를 받을 수 있는 문제였다. 처음 접해보는 알고리즘이다보니 어떻게 풀어야할지 감이 잡히지 않아 다른 사람의 포스팅을 보면서 투포인터의 개념을 익히고 문제를 풀어보면서 투포인터의 동작 과정을 이해하였다. 

 

*** 투포인터 알고리즘

1. 배열의 인덱스를 가리키는 두 개의 변수를 만들어야 한다. 시작지점을 가리키는 startPoint, 끝지점을 가리키는 endPoint가 이에 해당한다.

2. 처음 startPoint와 endPoint는 0으로 초기화한다. 

3. startPoint와 endPoint까지의 합인 sum과 찾고자 하는 m값을 비교하면서 endPoint가 배열의 끝에 도달할 때까지 아래 과정을 반복한다. 

-> sum>=m : sum을 줄이기 위해 startPoint를 1증가시키고, startPoint의 배열 값을 sum에서 제외시킨다. 

-> endPoint==arr.length() : endPoint가 배열 끝에 도달했다면 반복문을 종료한다.

-> sum<m : sum을 늘리기 위해 endPoint를 1증가시기고, endPoint의 배열 값을 sum에 누적시킨다. 

-> sum==m : 조건을 만족하는 경우를 찾았으면 count를 증가시킨다.

 

 처음 접해보는 알고리즘이라 아직 이해도가 완벽하지 않기 때문에 좀 더 다른 유형의 투포인터 문제를 풀어봐야 할 것 같다.