[BOJ] 1806. 부분합 (🥇, 누적합/투포인터)

🔗

풀이

길이가 10만이기 때문에 투포인터로 풀이했다. i는 왼쪽 인덱스, j는 오른쪽 인덱스로 두고 값을 더할 때는 j에 있는 값을 더하고 j++를, 값을 뺄 때는 i에 있는 값을 빼고 i++를 하게 된다.

우선 시작할 때는 구간 내의 합인 s 가 기준값 S 보다 작으면 j에 있는 값을 더한다. 반대로 s 가 기준값 S 보다 크면 i에 있는 값을 뺀다. 기준을 충족하지 않으면 충족할 때까지 값을 더해나가고, 기준을 충족한다면 가장 짧은 길이를 구해야 하므로 가장 왼쪽의 값을 빼나가는 것이다. 기준을 충족하는 경우에만 짧은 길이를 업데이트 해주면 된다.

// 부분합 

package Baekjoon.Gold;

import java.util.Scanner;

public class baekjoon_1806 {
        static int N, S;
    static int[] arr;
    static int sol(int s) {
        if (s < S) {
            return 0;
        }

        s = 0;
        int i = 0, j = 0, minLen = arr.length;
        while (true) {
            if (s >= S) {
                // 기준을 충족하는 경우 1. 왼쪽 값을 빼고, 2. 왼쪽 인덱스 증가
                s -= arr[i];
                minLen = Math.min(minLen, j - i);
                i++;
            } else {
                // 기준을 충족하지 않는 경우. 1. 오른쪽 값을 더하고, 2. 오른쪽 인덱스 증가
                if (j >= arr.length) break;
                s += arr[j];
                j++;
            }
        }
        return minLen;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        S = sc.nextInt();

        arr = new int[N];
        int s = 0;
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
            s += arr[i];
        }

        System.out.println(sol(s));
    }
}