[백준] 1806번 부분합 (JAVA)

문제

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

1806번: 부분합

 

설명

수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구해야 한다.

일일이 부분합을 다 구해서 문제를 풀면 시간복잡도가 크게 나오기 때문에 투 포인터를 사용해 구한다.

두 개의 포인터를 각각 start와 end로 두고 둘 다 배열의 앞에서 시작한다.

현재 합이 S보다 작으면 현재 end가 가리키는 값을 더하고 end를 하나 전진시킨다. 해당 과정을 반복하다가 그 합이 S 이상이 되면 최소 길이를 최신화하고 현재 start가 가리키는 값을 빼고 start를 하나 전진시킨다.

위의 과정을 통해 배열 처음부터 끝까지 탐색하면서 부분합이 S 이상이 되는 것 중 최소 길이를 구할 수 있다.

void twoPointer() {
    int start = 0;
    int end = 0;
    int sum = 0;

    while (start <= N && end <= N) {
        if (sum >= S) {
            // 가장 최소가 되는 길이를 구한다
            minLength = Math.min(minLength, end - start);

            // sum에 nums[start]를 뺴고 start를 하나 전진시킨다
            sum -= nums[start++];
        }
        else {
            // sum에 nums[end]를 더하고 end를 하나 전진시킨다
            sum += nums[end++];
        }
    }

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

 

전체 코드

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

public class Main {

    static int N, S;
    static int[] nums;
    static int minLength;

    static void twoPointer() {
        int start = 0;
        int end = 0;
        int sum = 0;

        while (start <= N && end <= N) {
            if (sum >= S) {
                // 가장 최소가 되는 길이를 구한다
                minLength = Math.min(minLength, end - start);

                // sum에 nums[start]를 뺴고 start를 하나 전진시킨다
                sum -= nums[start++];
            }
            else {
                // sum에 nums[end]를 더하고 end를 하나 전진시킨다
                sum += nums[end++];
            }
        }

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        nums = new int[N + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        minLength = Integer.MAX_VALUE;

        twoPointer();
    }
}