2559번: 수열
첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기
www.acmicpc.net
문제
N일 동안 매일 아침 9시에 측정한 온도 데이터가 수열로 주어졌을 때, 연속 K일 동안의 온도 합 중에 가장 큰 값을 구하시오.
조건
2 <= N <= 100,000
1 < K < N
-100 <= 측정 온도 <= 100
시간제한 1초
풀이 방향
단순하게 모든 경우의 수를 탐색하여 문제를 해결한다면, 최악의 경우 (N == 100,000 && K == 2)
100,000 x (100,000 - 1) 회의 연산이 필요하며 대략 100억 회이다. 따라서 보다 효율적인 방법을 모색해야 하는데, 문제 조건이 '연속적인' 측정 온도의 합이라는 것에 주목해야 한다. 어떤 수열이 주어질 때 연속된 구간 합의 최대, 최소를 구하고자 할 때에는 구간 합을 사용할 수 있다.
구간 합에 대한 기본 원리는 백준 11659번 풀이 때 정리해두었으므로 해당 내용은 아래 링크에서 확인하자.
[백준] 11659번 - 구간 합 구하기 4
11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을
stonage.tistory.com
추가로 확인해야할 조건은 온도를 저장하는데 사용할 자료형인데 측정 온도가 -100 이상 100 미만 이므로 모든 날의 온도를 합이 -10,000,000 이상 10,000,000 이하이므로 int형을 사용해도 된다.
전체 코드
import java.util.*;
public class Main {
public static void main (String[] args) {
// 입력 시작
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
int[] data = new int[N+1];
for (int i=1; i<=N; i++)
data[i] = data[i-1] + sc.nextInt();
// 입력 끝
int max = Integer.MIN_VALUE;
for (int from=0; from+K<=N; from++) {
int to=from+K;
// 측정 온도의 from+1번 째 날부터 to번 째 날까지의 구간합
max = Math.max(max, data[to] - data[from]);
}
System.out.println(max);
sc.close();
}
}