142. 2559(수열)

import java.util.*;
import java.io.*;

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmp1 = br.readLine().split(" ");
		int N = Integer.parseInt(tmp1[0]);
		int K = Integer.parseInt(tmp1[1]);

		int[] numSum = new int[N + 1];
		ArrayList<Integer> numArr = new ArrayList<>();
		int sum = 0;

		String[] tmp2 = br.readLine().split(" ");

		for (int i = 1; i <= N; i++) {
			sum += Integer.parseInt(tmp2[i - 1]);
			numSum[i] = sum;
		}

		for (int i = K; i <= N; i++) {
			numArr.add(numSum[i] - numSum[i - K]);
		}

		Collections.sort(numArr);

		System.out.println(numArr.get(numArr.size() - 1));
	}
}

문제요약

측정한 온도 전체 날짜는 N이다. K는 합을 구하기 위한 연속적 날짜 수이다.

날짜 N 의 연속적인 날짜 K의 합은 얼마인가?

설명

누적합을 쓰면 매우 빠르게 문제를 풀 수 있다.

맨위는 입력받은 값이고 그 입력받은 값을 기준으로 누적합을 구하면 가운데 줄과 같다.

여기서 만약 2틀치를 받는 다고하자. 그러면,

다음 같이 누적합을 이용하여 값을 구할 수 있다.

 

이 코드를 짜면

		for (int i = 1; i <= N; i++) {
			sum += Integer.parseInt(tmp2[i - 1]);
			numSum[i] = sum;
		}

처음 값은 0으로 하고 값을 점차 추가시킨다.

 

		for (int i = K; i <= N; i++) {
			numArr.add(numSum[i] - numSum[i - K]);
		}

K번째 부터 시작한다.(0부터 해도 되지만 하면 식이 복잡해짐.)

인덱스가 [i] 의 누적합과 인덱스가 [i-K] 의 누적합을 빼주면 된다.

이 식은 결국  인덱스가 느린 것 - 빠른 것으로 해주는 것이다.

 

예를 들어 index 2 인 것 1 과 index 0인것 0 을 빼주면 1일차, 2일차 누적합은 1이 된다.

 

이런 식으로 끝까지 구하고 max를 통해 최대값을 구해주면 된다.