Algorithm/boj
백준 2559 c++
Mini_96
2023. 3. 1. 20:19
https://www.acmicpc.net/problem/2559
2559번: 수열
첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
int n, k,temp; //숫자, 연속일
int psum[100001];
int ret = -10000004; //최악의경우 : -100*10만번(n)
/*
* (-) 이중포문 : 100,000 * 100,000 ->시간초과
*
* 해결 :
* 구간쿼리는 psum!!!!!!!!!
* ex)
* 배열 : 1 2 3 4 5
* psum : 1 3 6 10 15
*
* for문은 i=k~n으로 돌리면됨.
* ret=max(ret,p[i]-p[i-k])
* ex) psum[3]-psum[3-3]
*/
int main()
{
cin >> n >> k;
/*
* a배열에 넣을필요없음. 바로temp로 덧셈
*
*/
for (int i = 1; i <= n; ++i) {
cin >> temp; psum[i] = psum[i - 1] + temp;
}
/*
* n=5(1,2,3,4,5)
* k=3
* idx: 0 1 2 3 4 5(n)
* psum : 0 1 3 6 10 15
*
* i=3~5
* psum[3]-psum[3-3]
* psum[4]-p[4-3]
* psum[5]-p[5-3]
*/
for (int i = k; i <= n; i++) {
ret = max(ret, psum[i] - psum[i - k]);
}
cout << ret;
}
이해가안되면 일단 외우자.