BOJ (Java) 1806번: 부분합

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

---

풀이

입력은 모두 자연수이므로 수를 더할 수록 값은 커지기만 한다.

또한 연속된 수열의 합이므로 주어진 배열의 순서를 바꾸면 안 된다.

투 포인터를 활용, end 인덱스를 늘려주며 부분합을 구하다가 합이 S가 넘으면 start 인덱스를 증가시키며 S가 넘는 부분합의 최소 길이를 찾는다.

---

Java 코드

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

public class Main {
    private static int N, S;
    private static int[] nums;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = bf.readLine().split(" ");

        N = Integer.parseInt(inputs[0]);
        S = Integer.parseInt(inputs[1]);

        inputs = bf.readLine().split(" ");
        nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(inputs[i]);
        }

        int minLen = N + 1;
        int start = 0;
        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += nums[i];
            
            // 합이 S가 넘었을 때 S가 넘는 최소 길이 구하기
            if (S <= sum) {
                while (S <= sum - nums[start]) {
                    sum -= nums[start];
                    start++;
                }
                
                // 최소 길이 갱신
                minLen = Math.min(minLen, i - start + 1);
            }
        }
        
        // 가능하지 않으면 0
        if (minLen > N)
            minLen = 0;
        
        System.out.println(minLen);
    }
}