[PS] 백준 #11509. 풍선 맞추기

문제 정보

• 난이도: 골드 V
• 문제 주소: https://www.acmicpc.net/problem/11509
• 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디

 

문제

큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다. 진솔이는 화살 가지고 노는 것과 사냥 연습하는 것을 좋아한다. 진솔이는 화살을 왼쪽에서 오른쪽으로 쏜다. 높이는 임의로 선택한다. 화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다. 화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다. 화살은 계속해서 가던길을 가는데 높이는 1 줄어든다. 그러므로 만약 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다.

우리의 목표는 모든 풍선을 터트리되 가능한한 적은 화살을 사용하는 것이다.

 

나의 풀이

브루트포스로 왼쪽 풍선부터 그 높이에서 하나씩 내려가면서 터뜨리려고 할 경우 최악에는 1+2+3+...+1,000,000번의 연산 즉, $O(n^2)$의 시간이 걸릴 수도 있다. 근데 "화살이 왼쪽에서 오른쪽으로 이동"한다는 조건이 있으므로, 한번에 모든 높이에서 화살을 쐈다고 생각해보면 $O(n)$ 시간만에 답을 구할 수 있다. 모든 화살들에 값 "0"을 배정해두고 풍선을 높이 h에서 만나면 h+1번 화살의 값을 1 감소시키고 h번 화살의 값을 1 증가시키면 된다. 물론 h+1번 화살의 값이 0이였을 경우 그 위에 화살이 없으므로 본인이 화살을 소모해야 하므로 cnt를 1 증가시킨다. 

#include <bits/stdc++.h>

using namespace std;

int main() {
	cin.tie(NULL);	cout.tie(NULL);	std::ios::sync_with_stdio(false);

	int n; cin >> n;
	vector<int> vec(n);
	for (int i = 0; i < n; i++) cin >> vec[i];
	
	int cnt = 0;
	vector<int> s(1000002, 0);
	for (int i = 0; i < n; i++) { // 왼쪽 풍선부터 확인
		int Hi = vec[i];
		if (s[Hi + 1] > 0) s[Hi + 1]--; // 원소 존재하는 경우
		else cnt++; // 원소 존재하지 않는 경우 (화살 소모)
		s[Hi]++;
	}
	cout << cnt;
}