백준 2559 java - 수열(누적합)

누적합을 활용한 문제이다.

시그마(sum)  시그마(1~N) - 시그마(1-M) = 시그마(M+1 ~ N)이라는 식만 알고 있으면 되는 문제이다.

<문제 풀이/접근과정>
1. N은 2이상 100,000이하, K는 1이상 N사이의 정수 -> int 자료형까지만 필요
2. 누적합을 이용해서 풀어봐야겠다
3. 입력 받는 즉시 바로 누적합으로 빼서도 구할 수 있겠군
4. sum 배열 다 구한 후에 또 for문 돌리면 시간 차이가 많이 나나?
5. 최솟값은 -20,000,000정도까지 나올 수 있겠군?

<ver 1 입력 받는 동시에 답 찾기>

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer stz =new StringTokenizer(br.readLine());
		int N = Integer.parseInt(stz.nextToken());
		int K = Integer.parseInt(stz.nextToken());
		int sum[] = new int[N+1];
		int answer = Integer.MIN_VALUE;
		stz = new StringTokenizer(br.readLine());
		
		for (int i = 1; i <= N; i++) {
			sum[i] = sum[i-1]+ Integer.parseInt(stz.nextToken());
			if(i >= K) {
				answer = Math.max(answer, sum[i]-sum[i-K]);
			}
		}
		System.out.println(answer);
	}
}

<ver 2 누적합 다 구한 후 누적합끼리 빼서 답 구하기>

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer stz =new StringTokenizer(br.readLine());
		int N = Integer.parseInt(stz.nextToken());
		int K = Integer.parseInt(stz.nextToken());
		int sum[] = new int[N+1];
		int answer = Integer.MIN_VALUE;
		stz = new StringTokenizer(br.readLine());
		
		for (int i = 1; i <= N; i++) {
			sum[i] = sum[i-1]+ Integer.parseInt(stz.nextToken());
		}
		
		for (int i = K; i <= N; i++) {
			answer = Math.max(answer, sum[i]-sum[i-K]);
		}
		System.out.println(answer);
	}
}

가볍게 풀 수 있는 문제였던 걸로 보인다.