BOJ 1806 부분합 자바 java

BOJ 1806 부분합 자바 java

 

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

1806번: 부분합

 

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

public class Main {
	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];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int point1 = 0, point2 = 0, sum = 0, ANS = 100001;
		while(true) {
			while(sum >= S) {	// 합이 S보다 작을 때까지 앞 포인터를 올린다.
				ANS = Math.min(ANS, point2-point1);
				sum -= arr[point1++];
			}
			if(point2 == N) break;
			sum += arr[point2++];	// S 보다 클 때까지 뒤 포인터를 올린다.
		} // while
		
		System.out.println(ANS == 100001? 0 : ANS);
	} // main
}

 

투포인터라는 알고리즘을 적용한 문제.

나는 처음 봐서 다른 사람들의 풀이를 보고 풀었다.

 

포인터를 두 개 두는데

point2(오른쪽)는 합이 S 일 때까지 쭉 증가하다가

S 이상이 되는 순간 point1(왼쪽)이 증가를 하면서 합이 S 이상이고 최대한 짧은 길이까지 늘어난다.