[백준] 2559번: 수열 - c++

수열

문제

입력

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.

출력

첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.

예제

문제 정의

이 문제는 누적합 배열을 이용해 풀면 된다.
먼저 최대값을 구하는 거니까 결과 값인 ret을 나올 수 있는 최솟값으로 초기화 해준다.
(-100*100,000)

psum 배열에 입력값에 대한 누적합을 저장하고
for문을 돌면서 k 구간만큼 누적합을 빼주면된다. 각 결과값중 최댓값을 ret에 업데이트하고 결과를 출력하면 된다.

#include<bits/stdc++.h> 
using namespace std;  

typedef long long ll;  
int n, k, temp, psum[100001], ret = -10000000; 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	cin >> n >> k; 
	for(int i = 1; i <= n; i++){
		cin >> temp; psum[i] = psum[i - 1] + temp; 
	} 
	// 0 3 1 -3 -12 -12 -9 -2 11 19 16
	// -6 13 -9 3 10 20 21 5 
	for(int i = k; i <= n; i++){
		ret = max(ret, psum[i] - psum[i - k]);
	}
	cout << ret << "\n";
    return 0;
}