[알고리즘]백준 1806: 부분합

 

풀이: 누적합&투포인터

특정 조건을 만족하는 연속된 부분 배열의 문제에서 누적합&투포인터의 개념이 많이 사용된다.

1) right 포인터는 0~N-1까지 증가면서 오른쪽으로 이동한다.

2) left 포인터는 s값이 주어진 조건보다 크다면 포인터를 오른쪽으로 계속 옮겨준다. 이는 주어진 조건이 자연수로 이루어진 길이 N의 수열이기 때문에 가능하다.

 

코드

import java.io.*;
import java.util.*;

public class Main1806 {
    public static int N,S;
    public static int[] arr;

    public static void main(String[] args) throws Exception {
        // 1. 입력 및 초기화
        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];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) arr[i] = Integer.parseInt(st.nextToken());

        // 2. 누적합, 투 포인터
        int answer = Integer.MAX_VALUE;
        int s = 0;
        int left = 0;
        for(int right=0; right<N; right++){
            s += arr[right];
            while(s>=S && left<=right){
                answer = Math.min(answer, right-left+1);
                s -= arr[left++];
            }
        }

        // 3. 출력
        if(answer==Integer.MAX_VALUE) answer=0;
        System.out.println(answer);
    }
}

 

 

https://www.acmicpc.net/problem/1806