BOJ01806 부분합

https://www.acmicpc.net/problem/1806 (opens new window)

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

투 포인터

투 포인터 (opens new window)

int start = 0;
int end = 0;
int sum = array[0];
int length = Integer.MAX_VALUE;
while (true) {
    if (sum >= s) { // (1)
        length = Math.min(length, end - start + 1); // (2)
        sum -= array[start++]; // (3)
    } else { // (4)
        end++; // (5)

        if (end == n) { // (7)
            break;
        }

        sum += array[end]; // (8)
    }
}

(1) 부분합 배열의 합 >= 구해야 하는 값인 경우이다.
(2) s이상인 경우 구간의 길이을 구해 최솟값을 갱신한다.
(3) 배열의 합을 감소한 뒤 start를 증가 시킨다.
(4) 부분합 배열의 합 < 구해야 하는 값인 경우이다.
(5) end를 이동한다.
(6) 만약 end가 배열의 index를 넘은 경우 반복문을 종료한다.
(7) 접근 가능한 index인 경우 배열의 합을 증가시킨다.

제출 코드

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ1896 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt(); // 10 <= n < 100_000
        // 0 < S <= 100_000_000. int 표현범위 -2,147,483,648 ~ 2,147,483,647
        int s = scanner.nextInt();

        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }

        int start = 0;
        int end = 0;
        int sum = array[0];
        int length = Integer.MAX_VALUE;
        while (true) {
            if (sum >= s) {
                length = Math.min(length, end - start + 1);
                sum -= array[start++];
            } else {
                end++;

                if (end == n) {
                    break;
                }

                sum += array[end];
            }
        }

        if (length == Integer.MAX_VALUE) {
            System.out.println(0);
            return;
        }

        System.out.println(length);
    }
}

#BOJ #두 포인터