[백준] 2559 수열

[백준] 2559 수열

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

틀린 풀이

• N은 2 이상 100,000 이하이다. K는 1과 N 사이의 정수이다.
  -> 아래와 같이 이중 for문으로 작성할 시 시간 복잡도 10^5 * 10^5
  -> 시간 초과

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, K;
	cin >> N >> K;

	vector<long long> temp;
	for (int i = 0; i < N; ++i) {
		long long input;
		cin >> input;
		temp.push_back(input);
	}

	long long maxSum = -1;
	for (int i = 0; i < N - K; ++i) {
		long long sum = 0;
		for (int j = 0; j < K; ++j) {
			sum += temp[i + j];
		}
		maxSum = max(maxSum, sum);
	}

	cout << maxSum;
	return 0;
}

C++ 풀이

• 연속적인 며칠동안의 온도의 합

• (i+1)번째 날 ~ (i+k)번째 날의 온도의 합
  = (i)번째 날 ~ (i+k-1)번째 날의 온도의 합 - (i)번째 날의 온도 + (i+k)번째 날의 온도

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, K;
	cin >> N >> K;

	vector<long long> temp;
	for (int i = 0; i < N; ++i) {
		long long input;
		cin >> input;
		temp.push_back(input);
	}

	long long sum = 0;
	for (int i = 0; i < K; ++i) {
		sum += temp[i];
	}

	long long maxSum = sum;
	for (int i = 0; i < N - K; ++i) {
		sum -= temp[i];
		sum += temp[i + K];
		maxSum = max(maxSum, sum);
	}

	cout << maxSum;
	return 0;
}