BOJ 1806 부분합

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

1806번: 부분합

import java.util.*;
import java.io.*;
public class Main
{
    
    public static int search(int[] acc, int s){
        int right = 0;
        int sum_length=acc.length+1;
        for(int left=1; left<acc.length; left++){
            int sum = acc[right]-acc[left-1];
            while(sum<s && right+1<acc.length){
                right+=1;
                sum = acc[right]-acc[left-1];
            }
            
            if(sum>=s && (right-left+1)<sum_length){
                sum_length = right-left+1;
            }
        }
        if(sum_length== acc.length+1) {
            return 0;
        }
        return sum_length;
        
    }
	public static void main(String[] args) throws IOException{
	    // 입력
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String[] input1 = br.readLine().split(" ");
	    String[] input2 = br.readLine().split(" ");
	    int n = Integer.valueOf(input1[0]);
	    int s = Integer.valueOf(input1[1]);
	    int[] numbers = new int[n];
	    for(int i=0; i<n; i++){
	        numbers[i] = Integer.valueOf(input2[i]);
	    }
	    
        //부분합 배열 만들기
        int[] acc = new int[n+1];
        acc[0] = 0;
        for(int i =1; i<n+1 ; i++){
            acc[i] = acc[i-1]+numbers[i-1];
        }
        
        //답 구하기
        int ans = search(acc, s);
        System.out.println(ans);
	}
}

나는 누적합을 구해놓고 풀잏여ㅑㅆ다.

하지만 누적합을 구할 필요가 없기도 하다.

 

import java.util.Scanner;

class Main
{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++)
            arr[i] = sc.nextInt();

        int ansLength = N + 1;
        int nextIndex = 0;
        int currentSum = 0;
        for (int i = 0; i < N; i++) {
            while (currentSum < M && nextIndex < N)
                currentSum += arr[nextIndex++];
            if (currentSum >= M) ansLength = Math.min(ansLength, nextIndex - i);
            currentSum -= arr[i];
        }

        if (ansLength > N) ansLength = 0;
        System.out.println(ansLength);
    }
}