[BOJ 1806] 부분합 (java)

1. 문제 : https://www.acmicpc.net/problem/1806

 

2. 풀이

투포인터 이용해서 최소값 찾는 문제

total이 s를 넘어가는 순간을 잡아서 min값을 계속 업데이트 해줌

 

3. 코드

import java.util.Scanner;

public class 부분합 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        int s = scan.nextInt();

        int[] nums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            nums[i] = scan.nextInt();
        }

        int min = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;
        int total = 0;
        while (start <= n && end <= n) {
            if (total >= s && min > end - start) min = end - start;

            if (total < s) total += nums[end++];
            else total -= nums[start++];
        }

        if (min == Integer.MAX_VALUE) System.out.println("0");
        else System.out.println(min);
    }
}