백준 24499

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

블롭은 $N$개의 애플파이 중 $K$개를 먹으려고 한다.
물론 블롭은 힘을 들이지 않고 먹고 싶기 때문에, 연속으로 배치되어 있는
$K$개의 애플파이를 먹으려 한다.
블롭을 도와서 블롭이 먹을 애플파이의 맛의 합의 최댓값을 구해 주자!

처음엔 그냥 이중 for문으로 풀었는데 시간초과가 나왔습니다.

다른 풀이를 보고서 놓친점이 있었습니다.

문제의 파이는 원형이였다.

문제의 파이는 원형이였기 때문에, N의 2배로 배열을 만들고 0부터 N-1까지의 합만 구하면 되는 문제였습니다.

파이는 i<n+k 만큼 반복하면 된다.

i는 2부터 6까지 확인하면 [2, 3, 4, 5, 2] 이렇게 반복하게 됩니다.

i=2 → sum += pies[2] - pies[0] → sum = [2,3]
i=3 → sum += pies[3] - pies[1] → sum = [3,4]
i=4 → sum += pies[4] - pies[2] → sum = [4,5] 원형
i=5 → sum += pies[5] - pies[3] → sum = [5,2] 원형

public class B24499 {
    public static void main(String[] args) throws IOException {
        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 pie[] =  new int [n];


        st = new StringTokenizer(br.readLine());
        for(int i = 0; i <n; i++){
            pie[i] = Integer.parseInt(st.nextToken());
        }

        // 함수 호출
        System.out.println(maxPieSum(n, k, pie));

    }


    public static int maxPieSum(int n, int k, int[] pie) {
        // 원형 배열 처리
        int[] pies = new int[2 * n];
        for (int i = 0; i < n; i++) {
            pies[i] = pie[i];
            pies[i + n] = pie[i];
        }

        // 초기 합
        int sum = 0;
        for (int i = 0; i < k; i++) sum += pies[i];
        int max = sum;

        // 슬라이딩 윈도우
        for (int i = k; i < n + k; i++) {
            sum += pies[i] - pies[i - k];
            max = Math.max(max, sum);
        }

        return max;
    }
}