[투포인터] 1806번 - 부분합

[백준] 1806번 - 부분합

📝 참고한 풀이

문제를 제대로 이해하지 못해서
다른 사람들의 풀이를 참고해서 문제를 풀었다.

• 현재 sum < S 인 경우
  오른쪽 끝 원소를 포함하고 right를 증가시켜 슬라이딩 윈도우를 확장한다.
• 현재 sum >= S 인 경우
  현재 부분 배열의 길이를 계산하고, 최솟값을 갱신한다.
  왼쪽 끝 원소를 제쇠하고 left를 증가시켜 슬라이딩 윈도우를 줄인다.
  

👩🏻‍💻 최종 코드

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

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());
		int S = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int[] numbers = new int[N+1];
		for(int i = 0; i < N; i++) {
			numbers[i] = Integer.parseInt(st.nextToken());
		}
		
		
		int left = 0;
		int right = 0;
		int sum = 0;
		int minLength = Integer.MAX_VALUE;
		
		while(left <= N && right <= N) {
			if(sum >= S) {
				minLength = Math.min(minLength, right - left);
				sum -= numbers[left++];
			}
			else if(sum < S){
				sum += numbers[right++];
			}
		}
		
		System.out.println(minLength == Integer.MAX_VALUE? 0 : minLength);
		
	}

}

---

Reference

백준 1806 부분합 (JAVA 자바 풀이)