첫 시도
- N이 100,000이라 완전탐색으로는 구현 불가능
- K가 10^8이라 만족도의 합이 int 범위를 넘어갈 확률이 높으므로 long 사용
- dp로 구현해보려고 했으나 실패
해결
- dp와 투포인터를 결합하여 해결
- left와 right로 범위를 만들고 범위 안 만족도의 합이 K를 넘어가면 left를 오른쪽으로 이동시키며 나뭇가지 끝까지 이동
- dp[0]을 arr[0]으로 초기화하고 이를 바탕으로 dp배열을 채움
- 시간복잡도는 left,right가 나뭇가지 끝까지 가는데 걸리는 시간이므로 O(2N)라고해도 무방
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int[] arr = new int[N];
for(int i = 0; i < N; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
long[] dp = new long[N+1];
long sum = arr[0];
int left = 0;
int rigth = 1;
while(rigth <= N){ // 투포인터 종료 조건 = right가 테이블의 범위를 벗어날 때까지
if(sum >= K){
while (sum >= K){
dp[rigth] = Math.max(dp[rigth],dp[left]+sum-K);
sum -= arr[left++];
}
}
else{
dp[rigth] = Math.max(dp[rigth],dp[rigth-1]);
if(rigth == N) break;
sum += arr[rigth++];
}
}
System.out.println(dp[N]);
}
}