[C++][Baekjoon][문자열] 2559 수열 (feat. prefix sum)

문제

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

2559번: 수열

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램

 

조건

N은 2 이상 100,000 이하

주어지는 수들은 모두 -100 이상 100 이하

 

 

 

예제 문제/답

10 2
3 -2 -4 -9 0 3 7 13 8 -3

10개의 수가 주어지고, 2일치를 연속적으로 더했을 때 갖 값,

 

=> 정답은 21

 

 

 

해결방법

첨에 규칙 찾아서 하려고 했는데, 인덱스를 잘못 계산했는지 이상한 값이 나왔다. 강의 답안 강이랑 누적합 개념 정리 영상보고 풀었다.

 

 

 

코드

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {

	int totalDay, continueDay, max = INT_MIN;

	cin >> totalDay >> continueDay;

	vector<int> temperates(totalDay + 1, 0);
	vector<int> psum(totalDay + 1, 0);

	for (int i = 1; i <= totalDay; i++) {
		cin >> temperates[i];
		temperates[i] += temperates[i - 1]; //prefix sum
	}

	for (int i = continueDay; i <= totalDay; i++) {
		int sum = temperates[i] - temperates[i - continueDay];
		if (sum > max) max = sum;
	}

	cout << max << "\n";

	return 0;
}

 

두번째 for 문에서 i 시작이 continueDay 이다. 기억하자.

 

 

 

 

누적합 참고 자료

[10주 완성 C++ 코딩테스트] 누적합, Prefix Sum