방과후
ALGORITHM NOTE약 1분

BOJ 1806 - 부분합

티끌 모아 태산

#algorithm#boj#gold#prefix-sum#two-pointers
아카이브로 돌아가기

문제 링크

문제

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

입력

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

출력

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

풀이

모든 수가 양수이기 때문에 구간 합이 S 이상이 되는지 여부는 투 포인터로 관리하기 좋다. 오른쪽 포인터를 늘려 합을 키우고, 조건을 만족하는 순간 왼쪽 포인터를 줄여 가능한 한 짧은 길이를 만든다.

현재 코드는 누적합 배열로 right와 left 사이의 구간 합을 바로 구한다. sum >= S일 때마다 정답을 갱신하고 왼쪽을 당기며, 각 포인터가 배열을 한 방향으로만 움직이기 때문에 전체는 선형 시간에 끝난다.

코드

java
import java.io.*;
import java.util.*;
 
public class Main {
 
    private static int N, S;
    private static int[] arr;
 
    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());
        arr = new int[N + 1];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++)
            arr[i] = arr[i - 1] + Integer.parseInt(st.nextToken());
 
        System.out.println(solve());
    }
 
    private static int solve() {
        int left = 0;
        int right = 1;
        int ans = Integer.MAX_VALUE;
 
        while (right <= N) {
            int sum = arr[right] - arr[left];
 
            if (sum >= S) {
                ans = Math.min(ans, right - left);
                left++;
            }
            else {
                right++;
            }
        }
 
        return (ans == Integer.MAX_VALUE) ? 0 : ans;
    }
}

복잡도

  • 시간 복잡도: 두 포인터가 각각 배열을 한 번씩 지나가므로 O(N)O(N)이다.
  • 공간 복잡도: 누적합 배열을 저장하므로 O(N)O(N)이다.

마무리

모든 수가 양수라서 오른쪽을 늘리면 합이 커지고 왼쪽을 줄이면 합이 작아진다. 이 단조성이 투 포인터로 최단 구간을 찾을 수 있게 해 준다.