꿈틀꿈틀 호석 애벌레 - 효율성 에서는 의 풀이로 가능했지만 이 문제에서는 은 최대 이기 때문에 불가능하다.
나뭇가지의 번째 위치에서 애벌레가 할 수 있는 선택은 두가지 뿐이다.
1. 먹이를 지나친다 2. 먹기 시작한다.
만약 어떤 칸에서 먹이를 먹기 시작한다면 애벌레가 지금까지 어떤 선택을 해왔건 간에 상관 없이, 다 먹고난 후에 쌓이는 탈피 에너지는 일정하다.
풀이에서는 매 칸마다 의 과정을 통해 그 칸에서 먹기 시작하면 쌓이는 탈피 에너지와 먹는 과정이 끝나는 칸을 구했는데, 이 과정에 이분 탐색을 동원할 수 있다.
각 칸마다 존재하는 먹이의 만족도는 0 이상의 정수이므로 는 가 정해져있을 때, 단조증가한다. 그러므로 이분 탐색을 이용하여 를 만족하는 가장 작은 를 구할 수 있다.
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));
}
}