[BOJ] 1806 부분합 Java 풀이

 

 

BOJ 1806 부분합

 

바로 직전에 풀었던 수들의 합2(2003번) 문제와 매우 유사하다. 
sdesigner.tistory.com/58

투 포인터로 S보다 큰 경우를 찾고, 경우의 수 대신 범위의 길이를 출력해주면 되겠다. 이번 문제에서도 N이 100,000인 경우 모든 원소가 10000이라고 해도 합이 약 10억이다. int형 변수를 사용하는데 문제가 없고 0.5초 시간 제한에도 딱히 문제가 없다.

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

public class Main {
	static int N, S;
	static int arr[];
	static int ans;
	static int start, end, sum;
	
	public static void main(String[] args) throws Exception {
		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+1];
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		start = 0; end = 0; sum = arr[0]; ans = 100001;
		while(true) {
			if(sum >= S) {
//				System.out.println("ans update");
//				System.out.println(end+"-"+start+"+"+1+"="+(end-start+1));
				ans = Math.min(ans, end-start+1);
				sum -= arr[start++];
			}else {
				sum += arr[++end];
			}
			if(end == N) {
				break;
			}
		}
		if(ans == 100001) {
			System.out.println(0);
		}else {
			System.out.println(ans);
		}
	}
}

 

역시 2003번 문제와 풀이가 매우 유사한데, 이번 문제는 경우의 수를 출력하는게 아니기에 cnt 변수 대신 ans 변수로 합 범위의 최솟값을 기록하려 했다. N의 최댓값이 100,000이므로 초기 셋팅을 100,001로 맞춰주었다. 이번 문제에서는 합이 S값보다 크거나 같으면 되기 때문에 sum >= S의 경우 ans를 업데이트해주는데, 합의 범위 길이를 가능한 짧게 만들어야 하기 때문에 앞의 범위(start pointer)를 하나씩 당겨오도록 했다.

수열의 모든 원소를 탐색하고 나왔는데 ans가 그대로 100,001이라면 조건을 만족하는 경우의 수가 존재하지 않는다는 뜻이기에 0으로 출력하고 이외 경우에는 ans를 출력하도록 했다.