[ 백준/Java ] 1806. 부분합

백준 링크 : https://www.acmicpc.net/problem/1806

 

🌱 [ 문제 요약 ]

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다.

이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중,

가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

( 조건 : 10 <= N <= 100,000 / 0 <= S <= 1억 )

 

🌱 [ 알고리즘 선택 ]

 

연속된 수들의 부분 합 = 누적 합

누적 합 직접 구현 ( n 제곱 = 10000 * 10000 = 1억 = 0.5초 불가능 )

투포인터를 통한 누적 합 표현 O(N)

 

🔥 [ 구현 방법 ]

 

End 포인터 증가 조건

 연속된 부분 합 S를 만족할 때까지 end 포인터를 증가 시킨다.

 

Start 포인터 증가 조건

만족한다면 start 포인터를 움직여 최소 길이를 구한다.

움직이는 조건은 start 포인터 인덱스의 값을 빼도 조건을 만족 하는지 물어본다.

만족 한다면 값을 빼고 start 포인터를 증가 시킨다. 조건이 불만족 될때 까지 반복 한다.

---

[ 전체 코드 ]

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Stream.of(br.readLine().split(" "))
        .mapToInt(Integer::parseInt).toArray();
        int numberCount = input[0];
        int targetSum = input[1];

        // 입력 받기
        int[] numberArr = Stream.of(br.readLine().split(" "))
        .mapToInt(Integer::parseInt).toArray();

        int start = 0;
        int end = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;

        while (end <= numberArr.length - 1) {
            sum += numberArr[end];
            if (sum >= targetSum) {
                while (targetSum <= sum - numberArr[start]) {
                    sum -= numberArr[start];
                    start++;
                }
                minLength = Math.min(minLength, end - start + 1);
            }
            end++;
        }
        System.out.print(minLength == Integer.MAX_VALUE ? 0 : minLength);
    }
}