백준 2559번 수열 C++로 구하기 feat 누적합

 

N개의 일수동안 온도를 재었다. K수의 온도값의 최대값을 구해야한다. 최대값을 구할떄는 기억해야할게있다.

 

1. 최대값을 구하기전에 최소값을 먼저구해야한다. 반대로 최소값을 구할때는최대값을 먼저구해야한다.

2. 정적배열에 데이터가 담기는것이다. 그러니 이때는 누적합이 생각이나야한다  prefix sum = psum!

 

그럼 바로 문제를 풀어보자

#include<bits/stdc++.h>
using namespace std;
int n,k,v,psum[100004],ret = -10000004;
    
int main() {
    cin >> n >> k;
    
    
    //누적합
    for(int i = 1; i<=n; i++)
    {
        cin >> v;
        psum[i] = psum[i-1] + v;
    }
    
    for(int i=k; i<=n; i++)
    {
        ret = max(ret,psum[i] - psum[i-k]);
    }
    cout << ret;
    
    
    
    
    return 0;
}

 

 

3번코드줄 설명  

 

ret = -1000만번인 이유는 온도는 +100 -100이라고하며 n은 최대 10만번이다 그러므로 10만X-100하면 -1000만번이다

그러나 정확하게 1000만번으로 하게되면 혹시모를 에러가있을수있으므로 +1이나 몇정도는 증가시키는게 좋다.

 

10번 코드줄 설명

 

누적합을 구할떄는 sum+= i로도 할수있으나 그럴경우 시간복잡도가 말도안되게 증가난다. 그렇기에 현재 누적배열을 구할떄는 이전누적배열 더하기 현재 값이나 배열이라면 배열을 더하면된다.

 

17번 코드줄 설명

 

max를 이용해서 최대값을 구한다. 구할때는 누적합의 쿼리 즉 n번에서 합해야하는 값 k번의 값을 누적시켜주면된다.

 

결과

 

 

어렵고 이해도 쉽지않지만 대단한개발자가 되기위해서는 더열심히해야한다.화이팅