[백준 3020번/c++] 개똥벌레

알고리즘

 

• 이분 탐색
• 누적 합

 

---

풀이

석순은 아래에서부터 종유석은 위에서부터 자란다.

이를 각각 bottom 벡터과 top 벡터로 나타낸다.

 

번갈아가면서 석순과 종유석의 길이가 입력되므로

차례대로 입력받은 값을 bottom 벡터 또는 top 벡터에 인덱스로 하여 1씩 더해준다.

 

실제로 석순의 길이가 3이라면 bottom[1], bottom[2], bottom[3]에 모두 1씩 더해주어야 하는데

이것을 이중 for문으로 다음과 같이 구현하면 시간 초과가 발생하므로 다른 방법을 사용하여야 한다.

 

시간 초과 코드

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

int main() {
	// freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n, h, len, cnt, min=2147000000;
	cin >> n >> h;
	vector<int> sec_cnt(h+1, 0);
	for(int i=1; i<=n; i++){
		cin >> len;
		if(i%2==0){
			for(int j=h; j>h-len; j--){
				sec_cnt[j]++;
			}
		} else{
			for(int j=1; j<=len; j++){
				sec_cnt[j]++;
			}
		}
	}
	for(int i=1; i<=h; i++){
		if(sec_cnt[i]<min){
			cnt=1;
			min=sec_cnt[i];
		} else if(sec_cnt[i]==min){
			cnt++;
		}
	}
	cout << min << " " << cnt;
	
	return 0;
}

 

 

즉, 누적합을 적용시키기 위해서는 석순 bottom은 위에서부터 아래로 합쳐가면서 벡터에 기록하면 된다.

종유석 top은 아래에서부터 위로 합쳐가면서 벡터에 기록하면 된다.

 

그러면 다음과 같은 코드가 완성된다.

 

성공 코드

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

int main() {
	// freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n, h, len, cnt, min=2147000000;
	cin >> n >> h;
	vector<int> top(h+1, 0), bottom(h+1, 0);
	vector<int> sec_cnt(h+1, 0);
	for(int i=1; i<=n; i++){
		cin >> len;
		if(i%2==0){
			top[h-len+1]++;
		} else{
			bottom[len]++;
		}
	}
	for(int i=h-1; i>=1; i--){
		bottom[i]+=bottom[i+1];
	}
	for(int i=2; i<=h; i++){
		top[i]+=top[i-1];
	}
	for(int i=1; i<=h; i++){
		sec_cnt[i]=bottom[i]+top[i];
		if(sec_cnt[i]<min){
			cnt=1;
			min=sec_cnt[i];
		} else if(sec_cnt[i]==min){
			cnt++;
		}
	}	
	cout << min << " " << cnt;
	
	return 0;
}