[BOJ/21318] 피아노 체조, c++

www.acmicpc.net/problem/21318

21318번: 피아노 체조

한줄 후기: 난 피아노 체르니 40까지 배웠다.

 

x, y 범위 내에서 a[i] > a[i+1] 인 개수를 찾는 문제이다.

다만 완전 탐색처럼 풀면 test case 별로 for 문을 돌아서 시간초과가 난다.

어떻게 알았냐면 나도 알고 싶지 않았다.

 

//AC
//BOJ 21318 피아노 체조

#include <iostream>
#include <vector>
using namespace std;
vector<int> piano;
int cnt[101010];
int main(){
	int n, tmp, t;
	cin >> n;
	for(int i=0; i<n; i++){
		scanf("%d", &tmp);
		piano.push_back(tmp);
		if(i==0)	continue;
		if(piano[i-1] > tmp)	cnt[i] = cnt[i-1] + 1;
		else cnt[i] = cnt[i-1]; 
	}
	cin >> t;
	while(t--){
		int x, y, ans = 0;
		scanf("%d %d", &x, &y);
		ans = cnt[y-1] - cnt[x-1];
		printf("%d\n", ans);
	}
	return 0;
}

시간 초과를 보고 이거 뭔가 처음에 난이도 받자마자 끝까지 다 기록해놔야 겠구나 하고 생각하다가 

누적합을 이용하면 된다는 걸 깨달았다.

난이도를 받을 때마다 바로 전 난이도랑 비교하고, 누적합을 cnt에 더해준다.

cnt => 1번부터 현재까지 실수할 악보 개수

 

x, y를 받으면 cnt[y]-cnt[x] 가 x-y 범위 내에서 실수하는 개수가 된다.

나는 0 index라 y-1, x-1로 해줬다. 시간 초과랑 사소한 것들만 주의해주면 되는 재밌는 문제