본문 바로가기
알고리즘/백준

1806번 - 부분합

by HWK 2024. 7. 4.

골드 5티어의 부분합이라는 문제이다.

제목과 문제가 같은데 K이상의 부분합을 가지는 가장 짧은 배열의 길이를 구하는 문제이다.

나는 입력부터 각 배열의 요소를 그대로 저장하기보다는, 해당 배열의 요소의 합을 누적해서 저장했다.

그렇게 저장한 배열의 요소중 K 이상이 되는 곳을 찾아 따로 저장해놓고,
K보다 작은 값이 나올때 까지 요소에서 요소를 빼줬다.

import java.util.*;

public class 부분합_1806번 {
    static int N, K;
    static int min = 100000;
    static int[] sumList;


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();

        sumList = new int[N];
        sumList[0] = sc.nextInt();
        if (sumList[0] >= K) {
            System.out.println(1);
            System.exit(0);
        }

        int bigger = 0;
        boolean find = false;
        for (int i = 1; i < N; i++) {
            int sum = sumList[i-1] + sc.nextInt();
            if (!find && sum >= K) {
                find = true;
                bigger = i;
                min = bigger+1;
            }
            sumList[i] = sum;
        }
        if(!find) {
            System.out.println(0);
            System.exit(0);
        }

        int start = 0;
        for (int i = bigger; i < N; i++) {
            for (int j = start; j < i; j++) {
                if (sumList[i] - sumList[j] >= K) {
                    min = Math.min(i - start, min);
                    start++;
                } else {
                    break;
                }
            }
        }

        System.out.println(min);
    }
}

골드치고 크게 어려운 문제는 아니었다.