[JAVA]백준_1806_부분합

문제링크

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

1806번: 부분합

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int S = 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());
		
//		System.out.println(Arrays.toString(arr));
		
		int start = 0;
		int end = 0;
		int minLen = Integer.MAX_VALUE;
		int sum = 0;
		
		while(true) {
			if(sum >=S) {
				minLen = Math.min(minLen, end-start);
				sum -= arr[start++];
			}
			else if(end == N) break;
			else if(sum <S) {
				sum +=arr[end++];
			}
		}
		
		System.out.println(minLen<Integer.MAX_VALUE?minLen : "0");
	}

}

 

for문 두개 돌려서 사용하면 시간초과가 뜬다.

따라서 투 포인터 사용해서 해결해야하는 문제다.

일차원 배열에서 start와 end 인덱스를 통해 해결하면된다.