BOJ 1806 - 부분합

문제

N개의 수로 이루어진 수열에서 합이 S 이상인 연속 부분 수열 중 가장 짧은 것의 길이를 구하라.

입력

첫째 줄에 N과 S, 둘째 줄에 N개의 수가 주어진다.

출력

최소 길이를 출력한다. 합이 S 이상인 부분 수열이 없으면 0을 출력한다.

예제

입력	출력
`10 15` `5 1 3 5 10 7 4 9 2 8`	`2`

풀이

투 포인터로 윈도우 합이 S 이상일 때 왼쪽을 줄이며 최소 길이를 갱신한다.

R 포인터를 오른쪽으로 이동하며 합에 더한다
합이 M 이상이면 최소 길이를 갱신하고 L 포인터를 이동하며 합에서 뺀다
R이 끝에 도달할 때까지 반복한다

핵심 아이디어: 양수 수열에서 투 포인터는 각 포인터가 최대 N번 이동하므로 O(N)에 최소 길이 부분합을 찾는다.

코드

package day649;
 
import java.util.*;
import java.io.*;
 
public class Day617BOJ1806부분합 {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int ans = 987654321;
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());
    int[] arr = new int[N];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++)
      arr[i] = Integer.parseInt(st.nextToken());
    int L = 0;
    int R = 0;
    int slide = 0;
    while (true) {
      if (slide < M) {
        if (R == N)
          break;
        slide += arr[R++];
      } else {
        ans = Math.min(ans, R - L);
        slide -= arr[L++];
      }
    }
    System.out.println(ans == 987654321 ? 0 : ans);
  }
}

복잡도

시간: O(N)
공간: O(N)

문제