백준 꿈틀꿈틀 호석 애벌레 - 효율성(20181)

꿈틀꿈틀 호석 애벌레 - 효율성

꿈틀꿈틀 호석 애벌레 - 효율성 에서는 $O(N^2)$의 풀이로 가능했지만 이 문제에서는 $N$은 최대 $10^5$ 이기 때문에 불가능하다.

나뭇가지의 $i$번째 위치에서 애벌레가 할 수 있는 선택은 두가지 뿐이다.
1. 먹이를 지나친다 2. 먹기 시작한다.
만약 어떤 칸에서 먹이를 먹기 시작한다면 애벌레가 지금까지 어떤 선택을 해왔건 간에 상관 없이, 다 먹고난 후에 쌓이는 탈피 에너지는 일정하다.
$O(N^2)$ 풀이에서는 매 칸마다 $O(N)$의 과정을 통해 그 칸에서 먹기 시작하면 쌓이는 탈피 에너지와 먹는 과정이 끝나는 칸을 구했는데, 이 과정에 이분 탐색을 동원할 수 있다.
각 칸마다 존재하는 먹이의 만족도는 0 이상의 정수이므로 $sum(i, j)$는 $i$가 정해져있을 때, 단조증가한다. 그러므로 이분 탐색을 이용하여 $sum(i, j) \ge K$를 만족하는 가장 작은 $j$를 구할 수 있다.

public class Main {
	static int N, K;
	static long[] S;
	static long[] cache;
	
	// 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;
	}
	
	// here부터 지나치거나 먹기 시작할 수 있을 때
	// 얻을 수 있는 최대 탈피 에너지
	static long dp(int here) {
		if (here >= N + 1) return 0;
		if (cache[here] != -1) return cache[here];
		long max = dp(here + 1); // 지나치는 경우
		// 먹기 시작하는 경우
		int tail = bin(here);
		if (tail != N + 1) {
			long sum = S[tail] - S[here - 1];
			max = Math.max(max, sum - K + dp(tail + 1));
		}
		return cache[here] = max;
	}
	
	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());
		S = new long[N + 1];
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 1; i <= N; i++) S[i] = S[i - 1] + Integer.parseInt(st.nextToken());
		cache = new long[N + 1];
		Arrays.fill(cache, -1);
		System.out.println(dp(1));
	}
	
}