백준 1806, 부분합 - 투 포인터

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

1. 아이디어

"연속된 수들의 부분합 ~"
=> 연속하다는 특징 이용가능하므로, 투 포인터 사용

---

• 2개의 포인터 ptr1, ptr2 모두 [0]에서 시작

• ptr2가 마지막 원소를 넘어갈 때까지 다음을 반복

1) 원소 합 < s 인 경우

• 원소 합 >= s 가 될 때까지, ptr2를 오른쪽으로 이동 (ptr2++)

2) 원소 합 >= s 인 경우

• 원소 합 < s 가 될 때까지, ptr1을 오른쪽으로 이동 (ptr1++)

2. 자료구조

• int s: 입력, 부분합 최소 목표
  => 10^8 (1억) << 21억 이므로, int 가능

3. 시간 복잡도

• 대략 반복문을 수열 길이만큼 반복: O(n)

코드

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

public class Main {
	static int n, s;			// 수열 길이 n, 부분합 최소 목표 s
	static int[] numbers;
	static int minLen = Integer.MAX_VALUE;		// 출력, 최소 길이
	static int sum;				// 수열의 합

	static void solution() {
		int ptr1 = 0;
		int ptr2 = 0;

		while (true) {
			if (sum >= s) {
				// 원소 합 < s 가 될 때까지, ptr1 을 오른쪽으로 이동 (ptr1++)
				sum -= numbers[ptr1];
				minLen = Math.min(minLen, ptr2 - ptr1);
				ptr1++;
			}
			else if (ptr2 == n)
				break;
			else		// sum < s && ptr2 != n
				// 원소 합 >= s 가 될 때까지, ptr2 를 오른쪽으로 이동 (ptr2++)
				sum += numbers[ptr2++];

			/* 조건문 순서를 다음과 같이하면 오류 발생
			 1) if (ptr2 == n)
			 2) else if (sum < s)
			 3) else	// ptr2 != n && sum >= s
			*/
		}
	}

	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());
		s = Integer.parseInt(st.nextToken());

		numbers = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			numbers[i] = Integer.parseInt(st.nextToken());

		solution();

		if (minLen == Integer.MAX_VALUE)
			System.out.println(0);
		else
			System.out.println(minLen);
	}
}