부분합 (Gold IV)

문제 링크

분류

누적 합(prefix_sum), 두 포인터(two_pointer)

문제 설명

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

문제 풀이

• 투포인터로 문제 접근
• sum이 S 보다 작으면 뒤의 포인터를 한칸 증가
• sum이 S 보다 크면 앞의 포인터를 한칸 증가
• 커질때마다 ans를 비교해서 작은 값으로 저장

Solution

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 S = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int totalSum = 0;

        int[] arr = new int[N];
        for (int n = 0; n < N; n++) {
            arr[n] = Integer.parseInt(st.nextToken());
            totalSum += arr[n];
        }
        if (totalSum < S) {
            System.out.println(0);
            return;
        }

        //투포인터로 구하기
        int s = 0;
        int e = 0;
        int sum = 0;
        int ans = Integer.MAX_VALUE;
        while (true) {
            if (sum >= S) {
                ans = Math.min(e - s, ans);
            } else if (e == N) {
                break;
            }

            if (sum < S) {
                sum += arr[e++];
            } else {
                sum -= arr[s++];
            }
        }

        System.out.println(ans);

    }


}