[Java] 백준 2559번 : 수열

문제

https://www.acmicpc.net/problem/2559

 

접근 방법

1. 연속적인 K일의 온도의 합이 최대가 되는 값을 출력하는 문제이다.
2. 따라서 브루트포스로 풀 경우, 연속하는 수열을 계속해서 더해주어야 한다.  따라서 브루트포스로 풀어도 되지만 누적합을 구해서 점과 점의 관계로 푸는 방법을 택했다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int N,K;
    private static int[]arr,prefix;
    private static int max = Integer.MIN_VALUE;

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        arr = new int[N+1];
        prefix = new int[N+1];

        st = new StringTokenizer(br.readLine());
        for(int i = 1 ; i <= N ; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            
            //누적합 배열
            prefix[i] = prefix[i-1]+arr[i];
        }
    }

    //실행
    public static void process() {
        //누적합 배열을 돌며 점과 점의 관계로 표현
        //(지금까지 다 더한값) - (해당 인덱스의 점까지 다 더한값)
        for(int i = K ; i <= N ; i++){
            max = Math.max(max,prefix[i]-prefix[i-K]);
        }
        System.out.println(max);
    }


    public static void main(String[] args) throws Exception {
        input();
        process();
    }
}