반응형
문제
https://www.acmicpc.net/problem/2559
2559번: 수열
첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기
www.acmicpc.net
풀이
투 포인터를 이용한다. l 인덱스 값을 증가시키면 이전 l 인덱스에 있던 값을 지우고 r 인덱스까지의 합을 구한다.
그 후 최대값을 비교하여 답을 구해간다.
수열에 음수도 나올 수 있으므로 처음에 최소값을 설정할 때 주의한다.
코드
java
|
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
|
import java.util.Scanner;
public class Main {
static int n, k;
static int[] a;
public static void main(String[] args) {
input();
solve();
}
private static void solve() {
int r = 0, sum = 0, res = Integer.MIN_VALUE;
for (int l = 1; l <= n - k + 1; l++) {
sum -= a[l - 1];
while (r + 1 <= n && r + 1 != l + k) {
r++;
sum += a[r];
}
res = Math.max(sum, res);
}
System.out.println(res);
}
private static void input() {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
a = new int[n + 1];
for (int i = 1; i <= n; i++)
a[i] = sc.nextInt();
sc.close();
}
}
|
cs |
반응형
'BOJ' 카테고리의 다른 글
| 백준 6416 - 트리인가? (0) | 2022.11.28 |
|---|---|
| 백준 1620 - 나는야 포켓몬 마스터 이다솜 (0) | 2022.11.18 |
| 백준 2003 - 수들의 합 2 (0) | 2022.03.17 |
| 백준 2110 - 공유기 설치 (0) | 2022.03.11 |
| 백준 1068 - 트리 (0) | 2022.03.10 |