[백준] 2559 수열 - 누적합(Prefix Sum) + 슬라이딩 윈도우(Sliding Window) JAVA

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

2559번: 수열

 

코드설명

누적합 문제입니다.

 

문제에서 유의해야할점은

1. PrefixSum = new int[N+1] 이기에 아래와 같이   i < N  - K +  1 까지 범위를 처리해야합니다.

for(int i=0;i<N - K + 1;i++) {
    int calculate = prefixSum[i + K] - prefixSum[i];
    answer = Math.max(answer, calculate);
}

2.온도값은 -100 이 최소수이고, N은 100000 이기에 100000 * 100 이 최소숫자입니다.

public static int answer = -100000 * 100;

코드

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

public class Main {
	
	public static int N, M, K, T;
	public static int answer = -100000 * 100;
	public static int[] arr;
	public static int[][] map;
	public static int[] prefixSum;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N];
    	prefixSum = new int[N+1];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    		prefixSum[i+1] = prefixSum[i] + arr[i];
    	}
    	
    	for(int i=0;i<N - K + 1;i++) {
    		int calculate = prefixSum[i + K] - prefixSum[i];
    		answer = Math.max(answer, calculate);
    	}
    	System.out.println(answer);
    	
	}
}

 

다른 형식으로 구현해본 누적합 코드입니다. 

prefixSum[i] = 0번째부터 i번쨰까지의 누적합을 저장한다.

import java.util.*;
import java.io.*;

public class Main {
    public static int N, K;
    public static long answer = Integer.MIN_VALUE;
    public static int[] arr;
    public static int[] prefixSum;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		arr = new int[N];
		prefixSum = new int[N];
		for(int i=0;i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		for(int i=0; i<N; i++) {
			prefixSum[i] = ( i == 0 ? arr[i] : prefixSum[i - 1] + arr[i] );
		}
		for(int i=K - 1; i<N; i++) {
			answer = Math.max(answer, prefixSum[i] - (i == K - 1 ? 0 : prefixSum[i-K]));
		}
		System.out.println(answer);
	}
}

 

슬라이딩 윈도우를 활용할 경우입니다.

import java.util.*;
import java.io.*;

public class Main {
    public static int N, K;
    public static long answer = Integer.MIN_VALUE;
    public static int[] arr;
    public static int[] prefixSum;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		arr = new int[N];
		prefixSum = new int[N];
		for(int i=0;i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int pSum = 0;
		for(int i=0; i<K-1; i++) {
			pSum += arr[i];
		}
		
		for(int i=K-1; i<N; i++) {
			pSum += arr[i];
			answer = Math.max(answer, pSum);
			pSum -= arr[i - K + 1];
		}
		
		System.out.println(answer);
	}
}