백준 2559 수열 문제 오답 분석

입력

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다. 

출력

첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.

---

제출결과 시간 초과. 실패

1차 수정 : sort 를 max_element 함수를 사용해서 시간을 개선해보려 함. 실패

2차 수정 : ios_base::sync_with_stdio(false)를 넣어 속도를 개선해보려 함. 실패

3차 수정 : hap의 크기 변경. -100의 온도를 10만번 더하면 그 값은 -1천만이고 그 값을 담기에는

hap의 자료형이 int면 안되기 때문. long long 형으로 수정, 벡터 su도 마찬가지. 실패

실패 원인 분석 : 10만번의 온도 수를 10만번 이상의 경우로 뽑은것을 다시 정렬하니 연산수가 많아 시간 초과가 걸리는 것

해결 방법 : 구간합을 이용하여 연산의 개수를 줄이도록 코드를 다시 만들자

max를 통해서 최대값을 구할때는 최소값을 구하고 그것과 비교하여 큰 것으로 갱신하고, min으로 최소값을 구할때는 최대값을 구하고 그것과 비교하여 작은 것으로 갱신하는 방법을 사용하자

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

int d_num;
int n;

vector<long long> su;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int r;
	long long hap=0;
	
	cin >> d_num;
	cin >> n;	
	vector<int> inp(d_num);
	
	for(int i=0; i<d_num; i++){
		cin >> inp[i];
	}
	for(int i=0; i<d_num-n+1; i++){
		for(int j=i; j<i+n; j++){
//			cout <<"i: " <<i << " / j: "<< j << "\n";
			hap += inp[j];
		}
//		cout << "여기까지 hap : "<< hap << "\n";
		su.push_back(hap);
		hap = 0;
	}
	long long answer = *max_element(su.begin(), su.end());
	cout << answer << "\n";
//	sort(su.begin(), su.end(), greater<int>());
//	for(int a: su)
//		cout << a << "\n";
//	cout << su[0];
		
	return 0;
}