백준 2559, 수열 - 투 포인터, 누적 합

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

1. 아이디어

"연속적인 며칠 동안의 온도의 합이 가장 큰 값 ~ ?"
=> 연속하다는 특징 이용 가능하므로, 투 포인터 사용

---

• 최초 앞에서부터 k 개의 합을 구함

• 2개의 포인터 ptr1, ptr2가 각각 [0], [k]에서 시작

• 다음을 ptr2가 [n-1]을 가리킬 때까지 반복
  1) 합에서 ptr1이 가리키는 값을 빼고, ptr1++
  2) 합에서 ptr2가 가리키는 값을 더하고, ptr2++

단순하게 for 문으로 각 숫자의 위치에서, 이후 k 개의 수를 더하는 알고리즘

• O(n x k)
  => n, k 최대값 대입: 10^5 x 10^5 = 10^10 >> 1억 (시간 초과!!)

2. 자료구조

• int: 출력, k개 값의 최대 합
  => 100 x 10^5 = 10^7 << 21억 이므로, int 가능

3. 시간 복잡도

• 대략 수열 길이 n만큼 반복문: O(n)
  => n 최대값 대입: 10^5 << 1억

코드

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

public class Main {
	static int n, k;				// 전체 날짜 수 n, 합을 구할 연속 날짜 수 k
	static int[] temperatures;		// 각 날짜 별 온도
	static int maxSum;				// 출력

	static void solution() {
		// 최초 k 개 합
		int temp = 0;
		for (int i = 0; i < k; i++)
			temp += temperatures[i];

		maxSum = temp;

		int ptr1 = 0;			// 합에서 뺄 위치
		int ptr2 = k;			// 합에서 더할 위치

		while (ptr2 <= n - 1) {
			temp -= temperatures[ptr1++];
			temp += temperatures[ptr2++];
			maxSum = Math.max(maxSum, temp);
		}
	}

	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());

		st = new StringTokenizer(br.readLine());
		temperatures = new int[n];
		for (int i = 0; i < n; i++)
			temperatures[i] = Integer.parseInt(st.nextToken());

		solution();
		System.out.println(maxSum);
	}
}