[백준 3020번 / C++ / 누적합] 개똥벌레

최근 프로젝트를 여러 진행하다보니 3개월 간 코테준비를 못하다가 이 문제를 시작으로 다시 준비하려고 한다. 

처음 이 문제에 접근했을 때 이중 for 문을 사용했다. (오랜만이라 시간 복잡도 생각도 안하고 접근... ) 

제한 시간은 1초인데, 시간 복잡도는 O(N*H) 이 걸린다.

1억번의 연산이 1초 정도니까  N ≤ 200,000, 2 ≤ H ≤ 500,000   

200000*500000 = 1조?  

 

이중 for문 돌리면 100퍼센트 시간 초과가 뜰거다. 

 

그렇기 때문에 한번의 루프로 이 문제를 해결해야한다. 

누적합을 사용해보자. 

 

#접근방법

 

석순이와 종유석은 bottom 과 top 에서부터 자란다.

먼저 번갈아가면서 길이가 입력한다고 하니 차례대로 bottom 벡터와 top 벡터에 입력받은 값을 인덱스로 보고 1씩 더해준다. 

 

여기서 누적합을 어떻게 사용하냐? 

석순이를 예로 들어서 설명하겠다. 

 

만약 석순이 벡터에 값이 

"2 0 3 1 " 라면,

길이가 1 인 석순 2개 

길이가 2 인 석순 0개

길이가 3인 석순 3개 

길이가 4인 석순 1개

뜻이다. 여기서 장애물을 파괴하는 수가 가장 작은것은 석순이 최대한 안겹치는 곳인 가장 긴 길이를 가진 애들인거다. 

즉, 누적합을 적용시킬려면 위에서부터 아래로 합쳐가면서 벡터에 기록하는 것. 

 

"6 4 4 1 "  벡터에 경신된 값. 

 

이 뜻은 첫번째 구간에서 6개 부셔야하고 두번째 구간에서는 4개 부셔야하고 ... 네번째 구간에서는 1개만 부수면 된다라는 뜻을 가진다. 

 

종유석도 위와 같은 방법으로 하되 반대로만 하면 된다. 

 

이후 result 벡터에 누적합을 적용시킨 bottom 벡터와 top 벡터를 합산해서 저장하고 

제일 작은값을 찾으면 된다. 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std; 
int n, h; 
int main() {
	cin >> n >> h;
	vector<int> bottom(h + 1, 0); 
	vector<int> top(h + 1, 0); 
	vector<int> result(h + 1, 0); 
	for (int i = 0; i < n / 2; i++) {
		int a, b; cin >> a >> b; 
		bottom[a]++; 
		top[h + 1 - b]++; 		
	}
	for (int i = h-1; i >= 1; i--) {
		bottom[i] += bottom[i + 1]; 
	}
	int min_num = 987654321;
	int cnt = 0; 
	for (int i = 1; i <= h; i++) {
		top[i] += top[i - 1]; 
		result[i] += top[i] + bottom[i]; 
		if (min_num > result[i]) {
			cnt = 1;
			min_num = result[i];
		}
		else if (result[i] == min_num)cnt++; 
	}
	cout << min_num << " " << cnt; 
}

 

3020번: 개똥벌레