문제 URL :https://www.acmicpc.net/problem/2559
2559번: 수열
첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기
www.acmicpc.net
문제접근법 :
수학적으로 접근한다면 n번째 까지의 합을 sum(n) = v[1]+. . .+v[n]이라 할때
연속적인 k번째까지의 합을 G라할때 G(n) = sum(n)-sum(n-k) 라는 공식이 성립합니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
//By 콩순이냉장고
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
int n, k;
int sum[100001];
int arr[100001];
void input() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
sum[i] = arr[i] + sum[i - 1];
}
}
void solve() {
int res = -1e9;
for (int i = k; i <= n; i++) {
res = max(res, sum[i] - sum[i - k]);
}
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 언제든지 댓글은 환영입니다.
'백준' 카테고리의 다른 글
| 백준 7662 이중 우선순위 큐 (0) | 2021.06.23 |
|---|---|
| 백준 16973 직사각형 탈출 (0) | 2021.06.23 |
| 백준 12930 두 가중치 (0) | 2021.06.17 |
| 백준 1080 행렬 (0) | 2021.06.17 |
| 백준 16958 텔레포트 (0) | 2021.06.17 |