[Algorithm] 수열

Jong Min ·2025년 4월 4일

algorithm

Algorithm

목록 보기

23/30

🏆 수열(백준 2559)

수열

📌 문제 설명

매일 측정한 온도가 정수로 주어질 때, 연속적인 K일 동안의 온도의 합이 가장 큰 값을 구하는 프로그램을 작성하시오.

예를 들어, 아래와 같이 10일간의 온도가 주어졌을 때

3 -2 -4 -9 0 3 7 13 8 -3

연속적인 2일 동안의 온도의 합은 다음과 같다

이 중 가장 큰 값은 21이다.

또한, 5일 동안의 연속적인 합을 구하면

이때, 가장 큰 값은 31이다.

🎯 입력 조건

2 ≤ N ≤ 100,000 (온도를 측정한 일 수)
1 < K < N (연속적인 일 수)
각 온도 값은 -100 ≤ X ≤ 100

📝 예제 입력 및 출력

// 입력
10 2
3 -2 -4 -9 0 3 7 13 8 -3

// 출력
21

💡 해결 방법

🔍 문제 접근

이 문제는 누적합(Sliding Window) 기법을 활용하면 효과적으로 해결할 수 있다.

처음 K일 동안의 합을 계산한다.
이후, 한 칸씩 이동하면서 맨 앞의 값을 빼고, 새로 추가되는 값을 더해가며 최댓값을 갱신한다.
시간 복잡도는 O(N), 즉 N번의 연산만으로 결과를 도출할 수 있다.

✅ 코드


/*
입력일때,
10 2
3 -2 -4 -9 0 3 7 13 8 -3
*/

class Main{
	public static void main(String[] args) throws IOException {
		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());

		arr[0] = Integer.parseInt(st.nextToken());

		for(int i = 1; i < N; i++){
			arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
		}

		// arr: 3 1 -3 -12 -12 -9 -2 11 19 16 (누적합)


		int max = arr[K-1]; // -1을 하는 이유는 배열 idx 맟추기 위해
		for(int i = K; i < N; i++) {
        	// max : -6 -13 -9 3 10 20 21 5 21 이러한 순서로 나옴
			max = Math.max(max, arr[i] - arr[i-K]);
		}

		System.out.println(max);




	}
}