[백준 / BOJ] 11509 풍선 맞추기

문제

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

11509번: 풍선 맞추기

높이가 같거나 다른 N개의 풍선이 직선에 있다.

화살을 날려 풍선을 터트릴 수 있는데, 한 풍선을 터트릴때마다 화살의 높이가 1만큼 낮아진다.

이때, 모든 풍선을 터트리기위해 필요한 화살의 최소횟수를 구하는 문제다.

---

풀이

아이디어?로 풀리는 문제였다.

풍선이 최대 1,000,000개 주어지기 때문에, 완전탐색으로는 풀 수 없다. 

문제를 풀기위해, 이전에 던져진 화살들의 위치를 기억하는 방식으로 풀었는데, 이러면 O(N)시간복잡도로 문제를 풀 수 있다. (혹은 입력과 동시에)

 

예를들어, arrows[idx] = idx위치에 떠있는 화살의 수 라고 할때...

문제의 예제 1번 입력의 경우

2 1 5 4 3

 

첫번째 풍선이 2번 위치에 있으므로, 2번위치에 화살을 던져 풍선을 터트린다. 풍선을 터트린 화살은 높이가 1 낮아져 1번 위치에 남아있게 되고, arrows배열은 arrows[1] = 1 로 변하게 된다.

두번째 풍선이 1번 위치에 있으므로 1번위치에 화살을 던져야하는데, 이미 1번위치에는 화살이 존재한다. 따라서, 추가적인 화살을 던지지않고, 두번째 풍선을 터트린후 arrows[1] = 0, arrows[0] = 1로 변하게 된다.

세번재 풍선이 5번 위치에 있는데, arrows[5] = 0 이므로, 화살을 던지지않으면 풍선을 터트릴 수 없다. 따라서, 추가적으로 화살을 던진후 arrows[4] = 1로 업데이트 해준다.

 

위 과정을 반복하면 풀린다.

 

주요 소스코드

	private int countNeededArrows(int[] balloons){
		int[] arrows = new int[this.getBalloonsMaximumHeights(balloons)+1];
		int neededArrows = 0;
		for(int balloon : balloons){
			if(this.isAlreadyThrowArrow(balloon, arrows)) this.downArrow(balloon, arrows);
			else{
				arrows[balloon-1]++;
				neededArrows++;
			}
		}
		return neededArrows;
	}

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/11509%20%ED%92%8D%EC%84%A0%20%EB%A7%9E%EC%B6%94%EA%B8%B0/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃