백준 11509번 풍선 맞추기

문제 링크입니다: https://www.acmicpc.net/problem/11509

처음에 Brute Force 방식으로 풀었기 때문에 TLE가 발생했습니다. 

사실 O(N^2)이기 때문에 시간 안에 풀 수 있을 줄 알았지만 문제에서 요구하는 시간 복잡도는 O(N)이였습니다.

이 문제의 핵심은 더 높은 곳에서 날아오는 화살의 존재 여부를 판단하는 것이였습니다.

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 1000000 + 1;

 

int N;

int arrowHeight[MAX]; //화살 높이

/*

int balloonHeight[MAX]; //풍선 높이

bool popped[MAX]; //풍선이 터졌는지 여부

 

int minArrow(void)

{

        int cnt = 0;

        for (int i = 0; i < N; i++)

        {

                 if (popped[i]) //이미 터져있다면

                         continue;

                 cnt++; //화살 숫자 증가

                 int height = balloonHeight[i];

                 for (int j = i; j < N && height; j++) //높이가 1이상일 경우에만 확인

                 {

                         if (balloonHeight[j] == height) //동일한 높이라면 터뜨린다

                         {

                                 popped[j] = true;

                                 height--; //풍선을 터뜨려야 높이가 감소

                         }

                 }

        }

        return cnt;

}

*/

 

int main(void)

{

        cin >> N;

 

        /*

        for (int i = 0; i < N; i++)

                 cin >> balloonHeight[i];

        */

        int height, cnt = 0;

        for (int i = 0; i < N; i++)

        {

                 cin >> height;

                 //(height+1) 높이에서 날아오는 화살이 없을 경우

                 //해당 높이에서 날아오는 화살 추가, 화살 갯수 추가

                 if (arrowHeight[height + 1] == 0)

                 {

                         arrowHeight[height]++;

                         cnt++;

                 }

                 //(height+1) 높이에서 날아오는 화살이 있는 경우

                 //높이가 1 감소

                 else

                 {

                         arrowHeight[height + 1]--;

                         arrowHeight[height]++;

                 }

        }

        //memset(popped, false, sizeof(popped));

        //cout << minArrow() << endl;

        cout << cnt << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~