[백준] 1806 - 부분 합(Java)

문제 파악

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

풀이

제목과 짧은 문제 덕에 문제 파악은 쉬웠다🙃. 부분 합 문제는 항상 투 포인터로 풀게 되는 것 같다.

왼쪽 & 오른쪽 인덱스를 변수로 잡아준 다음 오른쪽 인덱스는 계속 증가시키며 연속합 변수에 누적하여 더해준다.

안쪽 루프에서 연속합의 값이 S 이상이라면 왼쪽 인덱스를 오른쪽으로 조정해 주도록 하자.
이때 왼-오 길이를 계산하여 기존 길이보다 짧다면 업데이트해 주면 된다.

코드

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

public class N1806 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tok = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(tok.nextToken());
        int S = Integer.parseInt(tok.nextToken());
        tok = new StringTokenizer(br.readLine(), " ");
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(tok.nextToken());
        }
        int left = 0, sum = 0, minLength = Integer.MAX_VALUE;
        for (int right = 0; right < arr.length; right++) {
            sum += arr[right];
            while (sum >= S) {
                minLength = Math.min(minLength, right - left + 1);
                sum -= arr[left++];
            }
        }
        System.out.println(minLength == Integer.MAX_VALUE ? 0 : minLength);
    }
}