BOJ - 2003 ) 수들의 합 2

---

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

2003번: 수들의 합 2

 

---

투포인터 알고리즘 (Two-Pointer Algorithm)은 배열에 특정 구간에 대해 접근하여 처리할 경우, 

 

시간복잡도를 O(n^2) 에서 O(n) 까지 단축하는 알고리즘이다. 사실 알고리즘 자체는 어렵지 않다.

 

문제에서 원하는 특정 값을 m이라할때 배열의 인덱스를 가리키는 두개의 포인터변수를 선언한다.

 

그리고 특정 값보다 크면 첫번째 포인터변수를 증가시키고, 작으면 두번째 포인터변수를 증가시키고

 

하는 연산을 반복하면 선형시간내에 처리할 수 있다.

 

경우에따라서 투포인터는 

 

1 ) 처음 시작은 같이하고 배열의 끝인덱스로 향해가는 경우,

 

2 ) 하나는 배열의 첫인덱스에서 시작하고, 다른하나는 배열의 끝인덱스에서 시작하여 만나는경우

 

3 ) 하나는 배열의 첫인덱스에서 시작하고, 다른하나는 상황에 맞추어 이동시키는경우 ( 정렬되어있는 조건 )

 

의 경우에서 최적화를 할 수 있다. 아래 KOI 문제인 수들의합2는 1번 조건의 문제로 분류할 수 있다.

 

차례차례 2,3번의 문제도 풀어봐야겠다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 수들의합2 {

	public static void main(String[] args) throws Exception {
		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());
		long num[] = new long[n];
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < n ; i ++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		
		int start ,end , answer;
		long sum=num[0];
		answer = start = end = 0;
		for(;;) {
			if(sum == m) {
				answer++;
				end++; 
				if(end==n) break;
				sum+=num[end];
			} else if(sum > m) {
				sum-=num[start];
				start++;
			} else {
				end++;
				if(end==n) break;
				sum+=num[end];
			}		
		}System.out.println(answer);
	}
}

---