[백준] 2559 - 수열 (Java)

[백준] 2559 - 수열 (Java)

문제

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

풀이/후기

토요일에 예정된 코딩테스트에서 자주 나오는 유형이라길래 풀어보았다.

단순해보이지만 일반적인 반복문으로 풀이하면 런타임에러가 발생한다.

이 문제는 누적합과 두포인터 방법을 사용하여 풀 수 있는데, 나는 누적합을 이용해서 풀었다.

 

**배열에 담을 때 누적합으로 담기

**배열 인덱스 + 1 해주기

코드

package PrefixSum;

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

public class Problem2559 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(str.nextToken());
		int K = Integer.parseInt(str.nextToken());
		
		int[] arr = new int[N + 1];
		
		str = new StringTokenizer(br.readLine());
		for (int i=1; i<N+1; i++) {
			//누적합 더하기
			arr[i] = Integer.parseInt(str.nextToken()) + arr[i-1];
		}
		
		int max = Integer.MIN_VALUE;
		int temp = 0;
		for (int i=K; i<=N; i++) {
			temp = arr[i] - arr[i-K];
			if (temp > max) max = temp;
		}
		
		System.out.println(max);
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/b52bb025bee44102190f867fc94587d4f1498206

참고

https://nahwasa.com/entry/%EC%9E%90%EB%B0%94-%EB%B0%B1%EC%A4%80-2559-%EC%88%98%EC%97%B4-boj-java