[백준] 1806 부분합

문제 링크 : https://www.acmicpc.net/problem/1806

1806번: 부분합

 

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

// 누적합 + 투포인터
public class BOJ1806 {
    static int n, s;
    static int[] arr, dp;
    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());

        st = new StringTokenizer(br.readLine());
        arr = new int[n];
        dp = new int[n];    // 누적합 담는 배열
        for (int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            if (i==0){
                dp[i] = arr[i];
            }else {
                dp[i] = arr[i]+dp[i-1];
            }
        }

        int left = 0;
        int right = 1;
        int res = Integer.MAX_VALUE;

        while (right <= n){
            if (left >= n) break;
            int diff = dp[right-1] - dp[left] + arr[left];
            if (diff >= s){
                res = Math.min(res, (right-left));
                left ++;
            } else right++;
        }

        System.out.println(res == Integer.MAX_VALUE? 0 : res);

    }
}

 

해설 : 누적합을 미리 만들어 준 후에 투포인터를 이용하면 되는 문제이다.

오답노트 : while문의 종료 조건에서 한 번, 누적합 배열을 이용해서 수열의 연속된 합을 구하는 부분에서 조금 헤맸다.

처음 수열의 합을 diff = dp[right]-dp[left-1]로 했다가 배열 out of index 한번 맞고, 손으로 써가면서 다시 계산식을 구했다. 누적합에서 차이를 구한 후, left포인터가 가르키는 값을 더해줘야한다.