[백준] 12847 꿀 아르바이트 - 슬라이딩 윈도우(Sliding Window) + 자료형(Data Type) JAVA

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

코드설명

슬라이딩 윈도우(Sliding Window) + 자료형(Data Type) 입니다.

 

만약 for문으로 진행할경우 O(N^2) 이므로 10^10 의 시간복잡도가 나옵니다. 그러므로 슬라이딩 윈도우로 O(N)의 복잡도로 연산해야합니다.

 

또한, 처음에 제출했을때 바로 틀려서 어떤 로직이 문제였을까? 생각하는 과정에서 로직은 전혀 문제없었습니다.

문제점은 int형이 아닌 long형을 사용해야합니다.

Ti는 10^6까지, n은 10^5 입니다. 최악의 경우, 10^5 * 10^6 = 10^11 이므로, int형의 범위(+21억)를 넘어갑니다.  그러므로 long형으로 자료형을 수정합니다.

코드

package Main;

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

public class Main {
    private static int N, T, K, M;
    private static int[] arr;
    private static long answer = 0;
    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());
		M = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		long pSum = 0;
		for(int i=0;i<M-1;i++) {
			pSum += arr[i];
		}
		
		for(int i=M-1; i<N; i++) {
			pSum += arr[i];
//			System.out.println(pSum);
			answer = Math.max(answer, pSum);
			pSum -= arr[i - (M - 1)];
		}

		System.out.println(answer);
    }
    
    
}