백준 - 부분합 ( 1806번, JAVA )

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

풀이

• 두 포인터이기 때문에 시작점과 끝점을 i, j 로 놨다.
• 이후 부분합이 목표 합인 s보다 작은 경우 부분합을 늘려주면서 끝점을 증가 시켜준다.
• 만약 부분합이 목표합고가 같거나 더 크다면 끝점과 시작점의 길이를 구해주고 부분합을 시작점에 값만 빼주고 시작점을 증가시킨다.
• 처음 풀었을 때 while문 하나로 (j < n && i<=n) 이 조건으로 풀었더니 71%에서 틀렸다고 떠서 질문게시판을 가니 반례가 있었다..
• 1 1 1 1 1 1 1 1 1 10 / n =10 / s =10
• 이조건으로 디버깅 해보니 j가 마지막 인덱스에서 10이 되며 while문 조건에 충족하지 않아 바로 탈출 후 0을 반환
• while문을 두개로 나눠 만약 부분합이 s보다 크거나 같다면 그 안에서 while문으로 최소 길이를 찾게 수정했다 😮 조건에 유의하자 ✔

package problem_solving.greedy;

import java.util.Scanner;

public class BaekJoon_1806 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = Integer.parseInt(sc.next());
		int s = Integer.parseInt(sc.next());


		int [] arr = new int [n];

		for(int i= 0 ; i < arr.length ; i++) {
			arr[i] = Integer.parseInt(sc.next());
		}

		int i = 0 ; 
		int j = 0 ;
		int sum = 0 ;

		int len = Integer.MAX_VALUE;

		while(  j < n ) {
			if (sum < s) {
				sum += arr[j++];
			}
			while (sum >= s) {
				len = Math.min(j - i, len);
				sum -= arr[i++];
			}

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

}