수열의 길이 은 최대 이기 때문에 모든 연속부분수열을 순회하는 방법 으로는 불가능하다.
종만북에서 제시한 알고리즘의 최적화는 다음과 같다
모든 연속부분수열을 수열의 시작 지점에 대응시킨다. 그리고 어떤 연속부분수열에 대해 합이 이상이 되는 가장 짧은 구간만을 "후보 구간"으로 정의하여 고려한다. 시작 지점이 정해져있다면 , 이 후보 구간 외에는 답이 될 수 없다.
1) 여기서 후보 구간의 길이를 늘린다면 절대로 정답이 될 수 없다.
2) 여기서 후보 구간의 길이를 줄인다면 수열의 원소는 자연수이므로 합 미만이 되어 정답이 될 수 없다.
후보 구간을 시작 지점에 대해 오름차순 정렬하면, 시작 지점 가 증가하면 이 감소할 수 없음을 알 수 있다.
1) 가 증가했을 때, 이 감소하면 이전의 후보 구간에 포함되게 된다. (이전의 후보 구간보다 이 최소 1만큼 더 작을 것이다) 이 구간의 합은 보다 작기 때문에 후보 구간이 될 수 없다.
구간의 끝은 계속해서 유지하면서 모든 연속부분수열을 순회하면 최적해를 찾을 수 있다.
시간복잡도
반복문이 2개 겹쳐있으니까 으로 생각할 수 있는데, 반복문 안의 while문은 head와 상관없이 이므로 으로 이 된다.
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 난이도 기여하려고 보니 알고리즘 분류로 이분 탐색과 부분합을 투표하신분도 있었다. 그 순간 풀이가 생각났다. 조금 고민해봤었으면 풀 수 있었을텐데
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);
}
}