[백준] 1806 부분합 - 누적합(Prefix Sum) + 투포인터(Two Poitner) JAVA

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

1806번: 부분합

코드설명

누적합과 투포인터를 활용하여 진행합니다.

 

문제로직입니다.

1. 먼저 누적합을 구해줍니다. ( 부분합 중에 그 합이 S 이상이 되는것을 구하기에 누적합을 구합니다. )

2. 누적합에서 투포인터를 활용하여 합 S보다 커질때까지 end 포인터를 계속해서 이동시킵니다. 

3. S보다 커졌다면, 부분합 중 S 이상이 되는 것 중 가장 짧은것의 길이를 갱신처리합니다.

4 .이제 start++ 처리를 통해 부분합의 크기를 줄여나갑니다.

5. 3번과 4번 과정을 계속진행합니다.

6. 계속해서 진행하다보면, start가 N보다 커지게 되고 종료됩니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static int N, S;
	public static int[] arr;
	public static int[] prefixSum;
	public static int answer = Integer.MAX_VALUE;
	
    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];
    	prefixSum = new int[N+1];
    	
    	arr = new int[N];
    	int sumValue = 0;
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    		sumValue += arr[i];
    		prefixSum[i+1] = sumValue;
    		
    	}
    	
		int start = 0;
		int end = 0;
		int sum = 0;
    	while(start < N) {
    		while(sum < S && end <= N) {
    			sum = prefixSum[end] - prefixSum[start];
    			end += 1;
    		}
    		if(sum >= S) { //만약 S가 sum보다 더 크거나 같다면, answer값과 길이를 비교해야합니다.
    			answer = Math.min(answer,  end - start - 1); //end +=1 로 된 상태로 넘어오기에, -1 을 처리합니다. 
    		}
			sum -= arr[start];
			start += 1;	
    	}
    	
    	if(answer == Integer.MAX_VALUE) {
    		System.out.println("0");
    	}else {
    		System.out.println(answer);
    	}
    }
}