22번

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


int main() {
   int N = 0;
   int K = 0;
   int Z = 0;
   int sum = 0;
   int max= -2147483648;
   cin >> N;
   cin >> K;
   Z = (N - K) + 1;
   vector<int> arr(N);
   vector<int> arr2(Z);
   for (int i = 0; i < N; i++)//숫자 입력
   {
      cin >> arr[i];
   }


   for (int i = 0; i < Z; i++)
   {
      sum = 0;
      for (int j = i; j < K + i; j++)
      {
         sum = arr[j] + sum;
         arr2[i] = sum;
      }
      if (max < arr2[i])
      {
         max = arr2[i];
      }
      
   }

   

   cout << max;

}

처음 2중 for문을 사용하였지만 타임리밋 발생

 

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


int main() {
	int N = 0;
	int K = 0;
	int Z = 0;
	int sum = 0;
	int max;
	cin >> N;
	cin >> K;
	vector<int> arr(N);
	for (int i = 0; i < N; i++)//숫자 입력
	{
		cin >> arr[i];

	}
	for (int i = 0; i < K; i++)
	{
		sum = sum + arr[i];
	}
	max = sum;
	for (int i = K; i < N; i++)
	{
		sum = (sum + arr[i]) - arr[i - K];
		if (max < sum)
		{
			max = sum;
		}
	}



	cout << max;

}

다음과 같이 수정후 타임리밋 발생 x

 

값을 더한 로직 방식

 

10 3(N,K) 을 입력한 경우 10자리중 3자리씩 끊어서 더한후 값을 비교한다

 

이때 

 

배열 012 123 234.. 이런식으로 다 더해서 비교하지말고

 

배열 012 더한 값을 sum으로 둔 다음

그 sum에 가장 앞에 배열을 빼고 그다음 배열의 값을 더해주면 배열 123의 값이 나옴

 

즉 

 

처음배열(0,1,2) sum값 = -3 다음배열(1,2,3) sum(-3) + (-9) -(3) = -15 이런방식으로 더해서 비교하는방식