백준 11509. 풍선 맞추기

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

11509번: 풍선 맞추기

 

처음 드는 생각은 가장 높은 높이 h를 찾고 그 이후에 h-1값이 있다면 1씩 감소시키면서 풍선을 터트리는 브루트포스 방법이다.

하지만 이방법은 가장 높은 높이 h를 찾은후에 h보다 1작은 값을 계속 찾아야하므로 O(n^2)의 시간복잡도를 갖게되고 n은 최대 1000000이므로 불가능하다.

 

그 후 생각해본것이 배열의 인덱스를 이용한 방법이다.

배열의 인덱스를 높이, 값을 해당하는 높이에 현재 존재하는 화살이라고 생각한다.

풍선의 높이들을 순회하면서 배열[풍선높이+1]이 0보다 크다면 해당 높이에 현재 화살이 있으므로 풍선을 터트릴수 있다. 따라서 배열[풍선높이+1]은 -1하고, 배열[풍선높이]는 +1한다.

배열[풍선높이+1]이 0보다 크지않다면 이미 쏜 화살중에 현재 풍선을 터트릴수있는 화살은 없으므로 새로운 화살을 쏴야한다. 즉 배열[풍선높이] +1 해준다.

 

예를들어 주어진 풍선들의 높이가 {2 1 5 4 3} 이라면 첫풍선부터 탐색을 시작한다

 

풍선높이: 2

arr[2+1] = 0 이므로 현재 풍선을 터트릴 이미 쏜 화살은 없다. 

따라서 arr[2]++ 

idx (화살높이)	1	2	3	4	5
화살갯수	0	1	0	0	0

 

풍선높이: 1

arr[1+1] = arr[2] = 1 이므로 현재 풍선을 터트릴 이미 쏜 화살이 존재한다. 

따라서 arr[2]--;  arr[1]++;

idx (화살높이)	1	2	3	4	5
화살갯수	1	0	0	0	0

 

풍선높이: 5

arr[5+1] = arr[6] = 0

arr[5]++;

idx (화살높이)	1	2	3	4	5
화살갯수	1	0	0	0	1

 

풍선높이: 4

arr[4+1] = arr[5] = 1

arr[5]--; arr[4]++;

idx (화살높이)	1	2	3	4	5
화살갯수	1	0	0	1	0

 

풍선높이: 3

arr[3+1] = arr[4] = 1

arr[4]--; arr[3]++;

idx (화살높이)	1	2	3	4	5
화살갯수	1	0	1	0	0

 

반복문이 끝난후 arr의 화살갯수를 새어주면 된다.

 

 

#include <iostream>
#define MAX 1000001
using namespace std;

int n;
int balloon[MAX];
int mark[MAX];

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

    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> balloon[i];

    for(int i = 0; i < n; i++)
    {
        int h = balloon[i];

        if(mark[h+1] > 0)
        {
            mark[h+1]--;
            mark[h]++;
        }
        else
        {
            mark[h]++;
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        ans += mark[i];
    }

    cout << ans;
}