[백준 3020] 개똥벌레 (C++)

문제 링크: https://www.acmicpc.net/problem/3020

3020번: 개똥벌레

1. 주의할 점

- 높이의 최대가 50만이여서 높이만큼 크기의 2차배열을 생성하지 않고 1차 배열 2개로 해결하려고 한다

- 종유석과 석순을 다른 배열로 입력받는다

- 각각 배열은 해당 높이가 들어올때(밑이나 아래 기준), '몇개의 장애물이 부서지는지'에 대한 정보를 담고 있다

 

2. 구현

- From_up[idx] : 위에서부터 높이가 idx일 때 부서지는 종유석의 수

- From_down[idx]: 밑에서부터 높이가 idx일 때 부서지는 석순의 수

- 벡터 V에는 높이 1부터 Height까지 높이가 H일때 From_down[H] + From_up[Height - H +1]을 모두 담은 후 Sorting한다.

- Sorting 이후에는 V의 첫 번째 원소와 같은 값을 지닌 원소가 몇개 있는지 세고 출력한다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int from_down[500001];
int from_up[500001];
vector<int> v;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int num, height, val;
	cin >> num >> height;
	for (int i = 0; i < num; i++) {
		cin >> val;
		if (i % 2 == 0) from_down[val]++;
		else from_up[val]++;		
	}
	for (int i = height-1; i >= 1; i--) {
		from_down[i] += from_down[i + 1];		//아래에서 부터 높이 i일때 부수는 장애물의 수
		from_up[i] += from_up[i + 1];			//위에서 부터 높이 i일때 부수는 장애물의 수
	}
	//밑에서부터 높이 i일때 부수는 장애물 수
	for (int i = 1; i <= height; i++)
		v.push_back(from_down[i] + from_up[height - i + 1]);
	sort(v.begin(),v.end());
	int dup = 1;
	int result = v[0];
	for (int i = 1; i < v.size(); i++) {
		if (v[i] == result) dup++;	
		else break;
	}
	cout << result << " " << dup;
	system("pause");
	return 0;
}