2559번: 수열(Java)

 

 

 

 구간 합을 이용하는 문제이다. 구간 합을 공부한 지 얼마 되지 않아 처음에 고민을 많이 했다. 

 

우선, 필요한 변수를 선언하고, 수를 입력받으며 구간합을 구한다.

Scanner scanner = new Scanner(System.in);
int size = scanner.nextInt();
int day = scanner.nextInt();
int[] arr = new int[size];
arr[0] = scanner.nextInt();
for(int i = 1; i<size; i++){
    arr[i] = arr[i-1] + scanner.nextInt();
}

 

 

 

그러고 나서 다음 아이디어를 적용시키면 된다.

 

 위는 입력에 대한 구간합과, 구간합 별로 어떤 수들을 더했는지 정리한 표이다. 만약 1 번째부터 3 번째 index의 합을 구하려면, (3 번째 구간합) - (0 번째 구간합)을 하면 된다. 3 번째 구간합 = 0 번째 구간합 + 1, 2, 3번째 입력값이기 때문이다.

 

 

코드로 보면 다음과 같다.

int max = arr[day-1];
for(int i = day; i<size; i++){
    max = Math.max(arr[i] - arr[i - day], max);
}

 

 

 

 

 

결과 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int day = scanner.nextInt();
        int[] arr = new int[size];

        arr[0] = scanner.nextInt();
        for(int i = 1; i<size; i++){
            arr[i] = arr[i-1] + scanner.nextInt();
        }

        int max = arr[day-1];
        for(int i = day; i<size; i++){
            max = Math.max(arr[i] - arr[i - day], max);
        }

        System.out.println(max);
    }
}