[BOJ] 1806 부분합 JAVA

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

1806번: 부분합

 

메모리 : 22,464kb
실행시간 : 236ms

 

문제분석

투 포인터

N^2 만 해도 시간초과
--> N 또는 logN 정도로 줄여야 함
--> 투 포인터

 

걸린시간

1시간 ⏱️

 

풀이방법

1. 입력 받으면서 누적합 저장
2. 투 포인터 (시작점, 끝점) 지정
3-1. 현재 범위 (시작점 ~ 끝점)의 누적합이 S보다 크거나 같을 경우 : 최소 길이 갱신, 시작점 한칸 옮기기
3-2. S보다 작을 경우 : 끝점 한칸 옮기기

 

포인트

시간초과 때문에 최대 N만에 끝내야함
투 포인터 쓰면 2N이라서 가능

 

코드

package study.day1020;

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

public class BOJ_1806_부분합 {		// 메모리 : 22,464 kb		실행시간 : 236 ms
	public static void main(String[] args) throws Exception {
		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 + 1];
		int len = Integer.MAX_VALUE;
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			arr[i] = arr[i - 1] + Integer.parseInt(st.nextToken());

		}

		int left = 0;
		int right = 1;
		while(right <= N) {
			if(arr[right] - arr[left] >= S) {
				len = Math.min(len, right - left);
				left++;
			} else {
				right++;
			}
		}

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