백준[BOJ] 11509번(풍선 맞추기) C++

https://www.acmicpc.net/problem/11509

---

문제 설명

임의의 높이에 있는 풍선을 화살을 쏘아서 최소한의 화살로 모든 풍선을 터뜨리는 것이다.

• 화살은 높이 H에서 일직선을 이동한다.
• 화살이 풍선을 마주친 순간, 풍선은 터져서 사라지고 화살의 높이는 1 줄어든다.

Ex)

5   O
4    O
3     O
2->O
1  O

높이가 위와 같이 2 1 5 4 3처럼 되어있다.

1. 화살은 처음 풍선의 높이인 2 높이로 쏴야하며 이 풍선을 맞고 화살은 1높이로 줄어들어 1 높이에서 일직선으로 이동한다. 그러면 1번 높이에 있는 풍선도 쏴서 터트릴 수 있다.
2. 화살 1개로 풍선 2개를 터트렸다.
3. 이제 다시 5 높이에 있는 풍선을 터뜨리기 위해 화살을 새로 쏴야 하며 높이 5의 화살을 터트리고 1 줄어들어 높이 4에서 일직선으로 이동한다. 높이 4에 있는 풍선을 터뜨리고 1 줄어들어 높이 3에서 일직선으로 이동한다. 그래서 높이 3에 있는 풍선을 터뜨린다.
4. 화살 1개로 높이 5, 4, 3에 있는 풍선을 터트릴 수 있다.
5. 총 2개의 화살로 모든 풍선을 터트렸다.

이렇게 보면 쉬워보이지만 만약 높이가 4 5 2 1 4 처럼 주어진다면??
Ex)

5  O
4->O    O
3
2   O
1    O

1. 높이 4에서 진행하여 풍선을 터트리고 높이 3에서 일직선으로 진행한다.(화살 1개 사용)
2. 높이 5에서 새로운 화살로 풍선을 터트리고 높이 4에서 일직선으로 진행한다.(화살 1개 추가->총 화살 2개)
3. 높이 2에서 새로운 화살로 풍선을 터트리고 높이 1에서 일직선으로 진행한다. 높이 1에 있는 풍선까지 터트린다.(화살 1개 추가->총 화살 3개)
4. 높이 4에 풍선이 하나 남아있는데 이거는 아까 1번에서 높이 5에서 풍선을 터트리고 높이 4에서 일직선으로 진행 중이던 화살에 맞아 터트릴 수 있다.(화살 추가 없음->총 화살 3개)
   이처럼 화살의 높이를 인덱스로 가지는 배열을 이용해 화살이 재사용 된 것인지 새로 화살을 쏘아야하는지 확인해야한다.

---

문제 접근

• 풍선의 높이가 주어질 때마다 화살의 개수와 높이를 업데이트 해줘야한다.
• 화살의 높이를 인덱스로 가지는 배열을 이용한다.
• 화살을 터트린 후 높이가 1 낮아지면서 계속 다른 풍선을 터트릴 수 있기 때문에 이미 발사된 화살을 재활용해야한다.

  C++ code

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

int arrow[1000001];  //배열의 값을 0으로 초기화하기 위해 전역으로 선언
int main() {

	int h;
	int n;
	int cnt = 0;    //화살의 개수를 세는 변수
	cin >> h;

	for (int i = 0; i < h; i++) {
		cin >> n;
		if (arrow[n+1]==0) {   //만약 풍선의 1높은 위치에 화살이 없다면 재활용할 수 없으므로
			cnt += 1;       //새로운 화살을 쏘아야함
			arrow[n] += 1;     //풍선을 터트리고 그 높이에 화살을 추가해줌
		} 
		else {        //풍선의 1 높은 위치에 화살이 있다면
			arrow[n + 1] -= 1;    //화살 재사용하고 높이 1 낮아졌으므로 원래 위치에 있는 화살을 1 감소시켜줌
			arrow[n] += 1;    //그리고는 1낮은 위치에 화살을 1증가시켜준다.
		}
	}
	cout << cnt;

}