[자바] 백준 5591 - 最大の和 (boj java)

문제 : boj5591

 

  n개의 데이터에서 연속된 k개의 합이 최대인 지점을 찾으면 된다. 두 가지 정도로 해볼 수 있다.

이하 예시는 다음 입력을 이용해 설명하겠다.

5 3
2
5
-4
10
3

 

1. 슬라이딩 윈도우

  처음 k개의 합을 구한다(A). k개의 윈도우를 옆으로 옮겨다니듯이 생각하면 된다. 그럼 윈도우를 우측으로 한 칸 이동한다면, 직전 윈도우 위치의 첫번째 위치의 값을 빼고 이번에 새로 추가된 값을 더해주면 된다. 이런식으로 이동하면서 최대값을 구하면 된다. O(N)

 

2. prefix sum

  입력을 받을 때 미리 누적합을 계산해둔다. 그렇다면 i번 인덱스에서 이전 k개 원소들의 합은 arr[i]-arr[i-k]가 된다. 이걸 i를 k부터(그래야 i-k가 0 미만으로 안내려갈테니) n까지 증가시키면서 최대값을 찾으면 된다.

 

이하 코드는 prefix sum을 이용해 짠 코드이다.

 

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] arr = new int[n+1];
        for (int i = 1; i <= n; i++) {
            arr[i] = arr[i-1]+Integer.parseInt(br.readLine());
        }

        int max = 0;
        for (int i = k; i <= n; i++) {
            max = Math.max(max, arr[i]-arr[i-k]);
        }
        System.out.println(max);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}