백준 11509. 풍선 맞추기

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

11509번: 풍선 맞추기

 

int형 배열에 현재 화살의 위치를 기억시키면 된다.

풍선의 위치가 다음과 같다면 

 

4 5 2 1 4 

 

첫번째 풍선의 높이는 4이고, 높이 4에는 화살이 없으므로 화살의 갯수를 증가시키고 

높이 4에 풍선을 떠뜨린후 화살은 높이 3이 되므로 높이3에 화살이 하나 있다는 것을 기록한다. 

0	1	2	3	4	5
0	0	0	1	0	0

 

다음 풍선은 높이 5이고, 높이 5에는 화살이 없으므로 화살 갯수를 증가시키고

높이 5-1=4에 화살의 갯수를 증가시킨다.

0	1	2	3	4	5
0	0	0	1	1	0

 

 

다음 풍선은 높이 2이고, 높이 2에는 화살이 없으므로 화살의 갯수를 증가시키고 

높이 2-1 = 1에 화살을 증가시킨다. 

0	1	2	3	4	5
0	1	0	1	1	0

 

다음 풍선은 높이 1이고, 높이 1에는 화살이 있다. 

높이 1의 화살을 이용해 풍선을 떠뜨렸으므로 높이 1의 화살의 갯수는 감소시키고  높이 1-0 = 0의 화살의 갯수를 증가시킨다.

0	1	2	3	4	5
1	0	0	1	1	0

 

마지막 풍선의 높이는 4이고, 높이4에는 화살이 있으므로 

높이 4의 화살의 갯수는 감소, 높이 4-1 = 3의 화살의 갯수를 증가시킨다.

0	1	2	3	4	5
1	0	0	2	0	0