백준 부분합(1806)

부분합(1806)

수열의 길이 $N$은 최대 $10^5 - 1$이기 때문에 모든 연속부분수열을 순회하는 방법 $O(N^2)$으로는 불가능하다.

종만북에서 제시한 알고리즘의 최적화는 다음과 같다

1. 모든 연속부분수열을 수열의 시작 지점에 대응시킨다. 그리고 어떤 연속부분수열에 대해 합이 $S$이상이 되는 가장 짧은 구간만을 "후보 구간"으로 정의하여 고려한다. 시작 지점이 정해져있다면 , 이 후보 구간 외에는 답이 될 수 없다.
   1) 여기서 후보 구간의 길이를 늘린다면 절대로 정답이 될 수 없다.
   2) 여기서 후보 구간의 길이를 줄인다면 수열의 원소는 자연수이므로 합 $S$미만이 되어 정답이 될 수 없다.

2. 후보 구간을 시작 지점에 대해 오름차순 정렬하면, 시작 지점 $head$가 증가하면 $tail$이 감소할 수 없음을 알 수 있다.
   1) $head$가 증가했을 때, $tail$이 감소하면 이전의 후보 구간에 포함되게 된다. (이전의 후보 구간보다 $tail$이 최소 1만큼 더 작을 것이다) 이 구간의 합은 $S$보다 작기 때문에 후보 구간이 될 수 없다.

3. 구간의 끝은 계속해서 유지하면서 모든 연속부분수열을 순회하면 최적해를 찾을 수 있다.

시간복잡도
반복문이 2개 겹쳐있으니까 $O(N^2)$으로 생각할 수 있는데, 반복문 안의 while문은 head와 상관없이 $O(N)$이므로 $O(N + N)$으로 $O(N)$이 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 K = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine(), " ");
		int[] S = new int[N];
		for (int i = 0; i < N; i++) S[i] = Integer.parseInt(st.nextToken());
		int tail = 0; int rangeSum = S[0]; int min = 100000;
		for (int head = 0; head < N; head++) {
			// head에서 시작하는 구간중 합이 K이상인 가장 짧은 구간을 찾는다
			while (rangeSum < K && tail + 1 < N)
				rangeSum += S[++tail];
			if (rangeSum >= K) min = Math.min(min, tail - head + 1);
			// tail은 그대로 유지하고 head를 전진
			rangeSum -= S[head];
		}
		System.out.println(min == 100000 ? 0 : min);
	}
	
}

이분 탐색 풀이

알고리즘 분류가 투 포인터로 되어있어서 바로 풀이를 참조했었다. solved.ac 난이도 기여하려고 보니 알고리즘 분류로 이분 탐색과 부분합을 투표하신분도 있었다. 그 순간 $O(NlgN)$풀이가 생각났다. 조금 고민해봤었으면 풀 수 있었을텐데

1. 위와 같다.
2. 어떤 시작 지점에 대해 후보 구간을 찾는 것은 이분탐색이 가능하다. 수열 $A$에 대해 부분합 $A[head,tail]$은 수열의 원소가
   자연수이기 때문에 언제나 증가하기 때문이다. 이분 탐색을 통해 합이 $S$이상인 가장 작은 $tail$을 찾는 과정은 $O(lgN)$에 가능하다.
3. $O(N)$의 시작 지점에 대해 $O(lgN)$의 이분 탐색을 진행하면 최적해를 찾을 수 있다.

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

public class Main {
	static int N, K;
	static int[] S;
	
	static final int INF = 100000;
	
	// S[head, tail]의 부분합 중에서 K를 넘는 가장 작은 tail을 찾는다
	static int bin(int head) {
		int lo = head - 1; int hi = N + 1;
		while (lo + 1 < hi) {
			int mid = (lo + hi) / 2;
			if (S[mid] - S[head - 1] >= K) hi = mid;
			else lo = mid;
		}
		return hi;
	}
	
	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());
		K = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine(), " ");
		S = new int[N + 1];
		for (int i = 1; i <= N; i++)
			S[i] = S[i - 1] + Integer.parseInt(st.nextToken());
		int min = INF;
		for (int head = 1; head <= N; head++) {
			int tail = bin(head);
			if (tail != N + 1) min = Math.min(min, tail - head + 1);
		}
		System.out.println(min == INF ? 0 : min);
	}
	
}