자료구조, 알고리즘

[백준] 2559 - 수열

heehminh 2023. 9. 27. 17:52
반응형

https://www.acmicpc.net/problem/2559

 

2559번: 수열

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기

www.acmicpc.net

 

알고리즘

누적합

 

풀이 

연속된 온도의 합이 최대가 되는 값: 구간합 prefix sum

psum[i] = psum[i-1] + a[i];

 

최대값을 구하라: 최솟값부터 최대값을 구하라 ( ret = max(ret, value); )

 

 

n 과 k 를 입력받은 후, 매일 측정한 온도를 배열 psum에 저장한다. psum[i]는 1부터 i까지의 온도의 누적합을 나타낸다. 

cin >> n >> k;
	
for(int i = 1; i <= n; i++){
    cin >> temp; 
    psum[i] = psum[i - 1] + temp; 
}

연속된 온도의 합이 최대가 되는 i 구하기

for(int i = k; i <= n; i++){
    ret = max(ret, psum[i] - psum[i - k]);
}

전체코드 

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

int n, k, temp, psum[100001], ret = -10000004;

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; 
	} 
	
	for(int i = k; i <= n; i++){
		ret = max(ret, psum[i] - psum[i - k]);
	}
	
	cout << ret << "\n";
	
	
	return 0;
}

 

 

반응형