[BOJ] 풍선 맞추기 11509번 C++

 

 

문제

큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다. 진솔이는 화살 가지고 노는 것과 사냥 연습하는 것을 좋아한다. 진솔이는 화살을 왼쪽에서 오른쪽으로 쏜다. 높이는 임의로 선택한다. 화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다. 화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다. 화살은 계속해서 가던길을 가는데 높이는 1 줄어든다. 그러므로 만약 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다.

우리의 목표는 모든 풍선을 터트리되 가능한한 적은 화살을 사용하는 것이다.

입력

첫 번째 줄에는 정수 N(1 ≤ N ≤ 1 000 000)이 들어온다.

두 번째 줄에는 배열 Hi가 N개 들어온다.

각각의 Hi(1 ≤ Hi ≤ 1 000 000)는 i번째 풍선의 높이에 해당하며 왼쪽에서 오른쪽으로 나열되는 순서이다.

출력

첫 번째 줄 한줄에 최소한 필요한 화살의 개수를 출력한다.

 

접근 방식

 

처음에는 풍선의 높이를 저장하는 벡터와 풍선이 터졌는지 여부를 확인하는  두개의 벡터를 이용해 풀이하였다.

하지만 이렇게 풀이한다면 반복문을 통해 매번 모든 풍선이 터졌는지 확인해야 했고

최대 N^2의 시간 복잡도로 시간초과가 뜨게 되었다

 

따라서, 다른 풀이를 고민하던 도중

map을 활용해 풀이하기로 하였다.

 

풀이 방식은 다음과 같다.

먼저 풍선의 높이를 모두 벡터에 저장한다.

 

그리고, for문을 통해 풍선을 순회하면서

현재 풍선의 높이에 맞는 화살이 있는지 확인한다.

이때, 화살이 있다면 해당 화살의 높이를 1 감소시키고

화살이 없다면, 새로운 화살을 추가하고, 해당 높이에 맞는 화살을 추가로 쏜다

최종적으로, 화살의 개수를 출력하면 된다.

 

이때, 화살의 높이와 개수를 unordered_map을 통해 관리해주면

최대 시간 복잡도가 N인 코드로 알고리즘 문제를 해결할 수 있다.

 

 

코드

#include<bits/stdc++.h>
using namespace std;

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

    int N;  cin>>N;

    vector<int> v(N);
    for(int i=0; i<N; i++) cin>>v[i];

    unordered_map<int,int> arrows;
    int cnt = 0;

    for(int i=0; i<N; i++) {
        int height = v[i];

        if(arrows[height] > 0) {
            arrows[height]--;
            arrows[height - 1]++;
        }
        else {
            cnt++;
            arrows[height-1]++;
        }
    }

    cout<<cnt;

}