[백준 11509] 풍선 맞추기

우선 가장 적은 화살로 풍선을 맞추려면

최대한 위에서 쏴서 한 화살로 여러개의 풍선을 맞출 수 있도록 해야한다

즉 한 화살로 최대한 여러개를 맞춰 모든 풍선을 없애는 쪽으로 짜면 된다

 

맨 초반에는 그냥 정직하게 짰다.

당연히 시간초과

 

하고 보아하니 N은 1000000까지 가능해서

O(N^2) 코드로 시간초과가 당연하다

#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

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

	int N; cin >> N;
	list<int> ballons; // 순서가 중요

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

	// 높은쪽에서 쏘는게 무조건 이득
	// 높은 놈을 알아야함
	int cnt = 0;
	while (!ballons.empty()) {
		list<int> temp = ballons;
		temp.sort(greater<>());

		int top = temp.front();
		auto it = find(ballons.begin(), ballons.end(), top);

		while (it != ballons.end()) {
			if (*it == top) {
				it = ballons.erase(it); // update iterator
				top--;
			}
			else {
				it++;
			}
		}
		cnt++;
	}

	cout << cnt;
	return 0;
}

 

 

그럼 시간초과가 안나기 위해서는 최소 O(N*logN) 으로 만들어야한다는 건데

생각해보니 입력을 받으면서 문제를 풀어나갈 수 있는 것 같았음

 

우선 화살은 앞 풍선부터 맞추니

뒤에 풍선차례로 갔을때는 화살들이 앞 풍선들은 모두 터트리고 온 화살들이다

즉 뒤 풍선을 맞추는걸 생각할때 앞 풍선에 대해 생각할 필요가 없는거임 

 

따라서 입력을 받을때마다 해당 풍선을 터트릴 수 있는 화살이 있는지 확인하고

없으면 해당 높이의 화살을 추가

있으면 해당 높이의 화살을 -1 해주면 된다.

 

#include <iostream>

using namespace std;

int arrows_num[1000000];

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

	int N; cin >> N;
	int x;
	
	for (int i = 0; i < N; i++) {
		cin >> x;
		// 풍선 맞출 수 있는 화살이 있으면
		if (arrows_num[x]) {
			arrows_num[x]--;
		}
		// x-1 높이의 화살 추가
		arrows_num[x - 1]++;
	}

	int cnt = 0;
	for (int i = 0; i < 1000000; i++) {
		cnt += arrows_num[i];
	}

	cout << cnt;
	return 0;
}

 

여기서 arrows_num 은 idx 높이에 있는 화살의 숫자다

만약 풍선을 맞출 수 있으면

idx 화살 숫자 -1 하고 idx-1 화살 숫자++ 해주면 된다