백준 1806번: 부분합[JAVA]

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

1806번: 부분합

 

 

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        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());

        int[] arr = new int[N+1];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int answer = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        int sum = 0;

        while (left <= N && right <= N) {
            if (sum >= S) {
                answer = Math.min(answer, right - left);
                sum -= arr[left++];
            } else if (sum < S) {
                sum += arr[right++];
            }
        }
        System.out.println(answer==Integer.MAX_VALUE ? 0 : answer);
    }
}

 

[설명]

투포인터 알고리즘을 활용한다.

sum 이 S보다 작을 경우 sum += arr[right++]를 하고

sum이 S보다 크거나 같을 경우 sum -= arr[left--]를 해준다. 그리고 동시에 right - left를 해주어 더 작은값을 출력해준다.