백준 2559 <수열>

투 포인터의 개념을 이용하여 접근이 가능한 문제!!

 

이 문제에서 조금 응용을 해 k일의 온도 합을 구하는 것이 T번 있다고 가정하면 인덱스 트리를 이용하게 되는 문제!

 

문제 풀이

1. 처음 K수만큼을 sum 값에 더한다.
2. start를 0 finish를 k로 두고 하나씩 증가하며 finish가 n이 될 때까지 진행한다.
3. sum값에 finish를 더하고 start를 빼주고 이렇게 최대를 구한다

전체 코드

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

public class Main{

	static int map[],n,k,result=Integer.MIN_VALUE;
	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());
		int start=0;
		int finish=0;
		map=new int[n];
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			map[i]=Integer.parseInt(st.nextToken());
		}
		int sum=0;
		for(;finish<k;finish++) {
			sum+=map[finish];
		}
		result=Math.max(result, sum);
		for(;finish<n;finish++) {
			sum-=map[start++];
			sum+=map[finish];
			result=Math.max(result, sum);
		}
		System.out.println(result);
		
	}

}