문제

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

---

풀이

브루트포스 문제에서 시간복잡도를 줄일 수 있는 몇가지 테크닉에 대해 이 포스팅에서 소개한 적이 있었다.

n개의 원소를 갖는 배열에서 '연속된 m개의 원소 합'을 구할 때 단순히 이중 반복문을 이용하면 O(NM)의 시간복잡도가 걸린다. 이 문제에서 1 <= M <= N, N은 최대 10만이므로 TLE가 발생한다.

이때 슬라이딩 윈도우라는 테크닉을 이용하면, O(N)에 연속된 m개의 합을 구할 수 있다.

슬라이딩 윈도우

참고: https://pinacle.tistory.com/87

#include <iostream>
#include <string> 
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll; 
typedef pair<int, int> pii;

const int MAX = 100001; 
int arr[MAX];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t, n, m, k; 

	cin >> t; 
	while(t--){ 
		cin >> n >> m >> k; 

		for(int i = 0; i < n; i++){
			cin >> arr[i];
		}

		int ans = 0, sum = 0; 
		int start = 0, end = m - 1; 
		for(int i = 0; i < m; i++){
			sum += arr[i];
		}

		if(n == m){ // 예외 처리
			cout << (sum < k ? 1 : 0) << "\n";
			continue; 
		}

		while(true){
			if(sum < k) ans++; 

			sum -= arr[start];
			start++; 
			end++; 

			if(end >= n) end = 0; 
			if(end == m - 1) break; 

			sum += arr[end];
		}

		cout << ans << "\n";
	}
	
	return 0;
}

유의사항

• n == m 인 경우에는 한칸씩 오른쪽으로 이동할 필요 없이, 그냥 n개의 합을 한번만 계산하고 k보다 작은지 비교하면 된다. (예외 처리 필수)
• 원형 배열이기 때문에 end >= n 이면 end = 0 으로 만들어주다가, end == m - 1 이 되면 처음과 같은 상태이므로 반복문을 종료한다. (종료 조건 파악하는 게 중요)