BOJ02435 기상청 인턴 신현수

https://www.acmicpc.net/problem/2435 (opens new window)

측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰값을 구한다.

누적합

누적합 (Prefix Sum, Cumulative Sum) (opens new window)

누적합을 이용해 해결하였다. 특정 구간을 가지는 모든 구간의 구간합을 비교하여 가장 큰 값을 구한다.

제출 코드

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ2435 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt(); // 온도를 측정한 전체 날짜의 수
        int k = scanner.nextInt(); // k는 합을 구하기 위한 연속적인 날짜의 수

        int[] temperatures = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            temperatures[i] = temperatures[i - 1] + scanner.nextInt();
        }

        int max = Integer.MIN_VALUE;
        for (int i = k; i <= n; i++) {
            max = Math.max(max, temperatures[i] - temperatures[i - k]);
        }

        System.out.println(max);
    }
}

#BOJ #브루트포스 알고리즘 #누적합