[백준/1806] 부분합 - JAVA

📌 문제

알고리즘 분류 : 누적합, 투포인터
난이도 : 골드4
출처 : 백준 - 부분합

🦧 문제 풀이 접근

수열을 배열에 담은 후 투포인터를 이용해 누적합을 구한다.

sum이 S보다 클거나 같을 경우 앞에 index를 +1,
S보다 작을 경우 뒤에 index를 +1

sum이 S보다 크거나 같은 경우, index사이의 거리의 최소 값을 구한다.

💻 code

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N =  Integer.parseInt(st.nextToken());
        int num =  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 s=0, e = 0;
        int min = 100_000_001;
        int sum = 0;
        while(s<=N && e<=N) {
            if(sum >= num && min>e-s) {
                min=e-s;
            }
            sum+=sum<num?arr[e++]:-arr[s++];
        }
        System.out.println(min==100_000_001?0:min);
    }
}

🥇 결과

🎓 느낀점

골드 문제지만 대표적인 누적합 문제라서 어렵지 않게 해결했다.