[백준][JAVA] 2559 - 수열

문제 출처 : https://www.acmicpc.net/problem/2559

2559번: 수열

 

 

 

문제

 

설명

가장 직감적으로 떠오르는 방법으로 구현을 했습니다만, 만약 N의 범위가 훨씬 커진다면 시간초과가 날 수 있는 코드입니다.

'Sliding Window'라는 기법을 이용한다면, window를 한칸씩 밀면서 공통되는 부분을 재사용하고 새롭게 빼지고 더해지는 원소만 계산함으로써 효율적으로 답을 구할 수 있습니다. 이와 관련된 코드는 제가 추후에 게시물을 올리면 밑에 링크 걸어두겠습니다!

 

 

 

코드

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

public class BOJ2599_Sequence {

	public static void main(String[] args) throws Exception {
		
		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[] arr = new int[N];
		st = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		} //입력 완료
		
		int start=0;
		int sum = 0;
		int max = Integer.MIN_VALUE;
		
		for(int i=0; i<N-K+1; i++) { //총 N-K+1번만큼 온도의 합이 계산됨
			for(int j=start; j<start+K; j++) { //연속 날짜의 수만큼 덧셈 연산
				sum+=arr[j];
			}
			max = Math.max(max, sum); //max값 업데이트
			start++; //start point 증가
			sum=0; //초기화!
		}
		System.out.println(max);
	}
}