문제

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

---

풀이

시간초과

N, Q 모두 최대 크기가 10^5 이므로 아래와 같이 매번 [s, e] 구간에서 난이도가 낮아지는 횟수를 카운트 하는 식으로 풀면, 시간 복잡도가 O(n^2)이 되어 TLE가 뜬다.

#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;

int N, Q;
vector<int> lv;

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

	cin >> N;

	for(int i = 0; i < N; i++) {
		int x; 
		cin >> x;
		lv.push_back(x);
	}

	cin >> Q; 
	while(Q--) {
		int s, e; 
		cin >> s >> e;
		
		// [s, e] 구간에서 난이도가 낮아지는 횟수 카운트 
		int cnt = 0;
		for(int i = s - 1; i < e - 1; i++){
			if(lv[i] > lv[i + 1]){
				cnt++; 
			}
		}
		
		cout << cnt << "\n";
	}
	
	return 0;
}

누적합

N개의 난이도를 입력 받으면서 동시에! 이제까지 난이도가 낮아진 횟수를 누적해서 배열에 저장해두면 [s, e] 구간에서 난이도가 낮아진 횟수를 O(N)이 아니라 O(1)에 구할 수 있다!

아래와 같이 뺄셈 연산만 해주면 되기 때문이다 :)

cnt[e - 1] - cnt[s - 1]

총 시간복잡도가 O(N)으로 줄어서 TLE가 발생하지 않는다. 누적합, 슬라이딩 윈도우, 투포인터 같은 스킬을 통해 시간복잡도를 낮추는 연습을 많이 해봐야겠다.

#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;

int N, Q;
vector<int> lv;
vector<int> cnt;

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

	cin >> N;
	lv.resize(N, 0);
	cnt.resize(N, 0);

	for(int i = 0; i < N; i++) {
		cin >> lv[i];
		if(i == 0) continue;

		// 이제까지 난이도가 감소한 횟수 누적해서 저장 
		if(lv[i - 1] > lv[i]) {
			cnt[i] = cnt[i - 1] + 1;
		}else{
			cnt[i] = cnt[i - 1];
		}
	}

	cin >> Q; 
	while(Q--) {
		int s, e; 
		cin >> s >> e;
		cout << cnt[e - 1] - cnt[s - 1] << '\n'; 
	}
	
	return 0;
}