[C/C++] 백준 2559번 수열

 

시간복잡도  O(n) -> 시간 초

#include <iostream>
#include <vector>


int main()
{
	std::vector<int> num;

	int start = 0;
	int sum = 0;
	int maxnum = 0;

	int n, k;
	std::cin >> n >> k;

	num.resize(n);

	for (int i = 0; i < n; i++)
	{
		int m;
		std::cin >> m;

		num[i] = m;
	}

	while (start != n-k)
	{

		for (int i = start; i < k+start; i++)
		{
			sum += num[i];
		}

		if (maxnum < sum)
		{
			maxnum = sum;
		}
		sum = 0;
		start++;
	}
	
	 
	std::cout << maxnum;

	num.clear();
}

 

 

 

 

정답 코드

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> num;

	int sum = 0;
	int maxnum = -999999999; // 가장 작은 수

	int n, k;


	std::cin >> n >> k;

	// 크기 고정
	num.resize(n+1);

	// 합 배열 만들기
	// 그전 합을 누적해 가며 vector에 저장
	for (int i = 1; i <= n; i++)
	{
		int m;
		std::cin >> m;

		num[i] = num[i - 1] + m;
	}

	// 가장 큰 값 계산
	for (int i = k; i <= n; i++) {
		sum = num[i] - num[i - k]; // 구간 합 계산 

		if (maxnum < sum)
		{
			maxnum = sum;
		}
	}

	std::cout << maxnum;
	num.clear(); // vector 값 정리
}