[BOJ/백준][Gold5] 11509 : 풍선 맞추기 (C++)

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

11509번: 풍선 맞추기

 

 

 

[난이도] Gold5
[유형] Greedy

[풀이]
O(N)에 0~N-1을 한번씩만 확인하면서 문제를 해결할 수 있습니다.
a[h] : 현재까지 a[h]에 위치하는 화살의 개수

현재 입력으로 v가 들어왔다면 a[v+1]을 확인해서 1 이상이면 v+1 위치에 화살이 내려와서
v의 풍선을 제거할 수 있습니다.
만약 a[v+1]이 0이라면 v 위치의 풍선을 제거할 풍선이 없으므로 v 높이로 화살을 날려야 하므로
정답에 1을 추가해줍니다.

 

#include <cstdio>
using namespace std;
int N,ans,a[1000001];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        int v;
        scanf("%d",&v);
        if(a[v+1]){
            a[v+1]--;
            a[v]++;
        }else{
            ans++;
            a[v]++;
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/11509.cpp