2559번: 수열
첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기
www.acmicpc.net
모든 연속적인 K일 간의 최대 온도의 합을 출력하는 문제입니다.
우선 dp를 이용하여 N일 간 측정한 모든 온도의 연속합을 저장합니다.
그 다음 투 포인터 방식으로 l = 1, r = K으로 시작하여 dp[r] - dp[l - 1]의 최댓값을 구해주시면 됩니다.
|
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.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int list[], dp[];
static int N, K, ans = Integer.MIN_VALUE;
static void func() {
int l = 1;
int r = K;
while (r <= N) {
ans = Math.max(ans, dp[r] - dp[l - 1]);
r++;
l++;
}
System.out.println(ans);
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
list = new int[N + 1];
dp = new int[N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
list[i] = Integer.parseInt(st.nextToken());
dp[i] = dp[i - 1] + list[i];
}
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > Two-Pointer' 카테고리의 다른 글
| boj 1253 좋다 (0) | 2021.10.21 |
|---|---|
| boj 9024 두 수의 합 (0) | 2021.10.21 |
| boj 17609 회문 (0) | 2021.03.29 |
| boj 1806 부분합 (0) | 2021.01.22 |
| boj 2003 수들의 합 2 (0) | 2021.01.22 |