[백준, 자바, 2559번] 수열 (누적 합)

풀이

• 누적 합 관련 문제를 푼지 시간이 좀 지나서
• 다시 해봤는데... 역시 알고보면 간단한데
• 헤맬땐 왜 이렇게 복잡한지...
• 그냥 단순히 누적 합을 구한 배열에서 특정 범위의 합이 알고 싶다면
• 누적 합 배열의 현재 위치에서 따른 특정 거리의 위치의 값을 빼주면
• 원하는 구간의 누적 합을 알 수 있다는 거...
• 예를 들어 li = [0, 3, 1, -3, -12, -12, -9, -2, 11, 19, 16] 이렇게 누적 합을 구했다면
•  5일 차이의 경우에 3일 차라면 li[3-1+5]-li[3-1] 이렇게 해서 -3이 되는 것.
• 3-1은 인덱스가 0부터 시작이기에 그럼
• 그래서 아래와 같이 해결.

 

// 1 방법

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] li = new int[N];
        li[0]=sc.nextInt();
        for (int i=1; i<N; i++) {
            li[i]=li[i-1]+sc.nextInt();
        }
        int mx = li[K-1];
        for (int i=0; i<N-K; i++) {
            mx = Math.max(mx,li[i+K]-li[i]);
        }
        System.out.println(mx);
    }
}

// 2 방법

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] li = new int[N];
        int[] check = new int[N+1];
        for (int i=0; i<N; i++) {
            li[i]=sc.nextInt();
            check[i+1]=li[i]+check[i];
        }
        int result = Integer.MIN_VALUE;
        for (int i=0; i<=N-K; i++) {
            result = Math.max(result, check[i + K] - check[i]);
        }
        System.out.println(result);
    }
}