[BOJ] 백준 11509번: 풍선 맞추기

풍선 맞추기

문제

N개의 풍선이 일렬로 놓여있고 화살을 쏴서 풍선을 맞추는 데 모든 풍선을 터트릴 수 있는 최소 화살의 개수를 구하는 문제이다. 화살은 처음 h 높이로 쐈다면 풍선 하나를 터트리면 h-1 높이로 바뀌어서 계속 날아간다. 화살은 왼쪽에서 오른쪽으로 쏜다.

문제 풀이

i번째 풍선을 직접 맞출지 다른 풍선을 거쳐서 맞추는지는 이 i번째 풍선 왼쪽으로 a[i]+1의 값을 가진 풍선을 맞췄는지 안 맞췄는지를 체크해주면 된다. 안 맞췄다면 i번째 풍선은 직접 화살을 쏴서 맞춰야 하는 풍선이므로 화살 개수를 ++해주면 된다. 아닌 경우는 a[i]+1의 값을 가진 풍선을 없는 것으로 바꾸고 a[i] 값의 풍선이 맞췄음을 갱신해주면 된다. 1차원 배열로 구현할 수 있다.

소스 코드

#include <bits/stdc++.h> using namespace std; int n; int st[1000001]; int main(){ scanf("%d", &n); int cnt=0; for(int i=0;i<n;i++){ int in; scanf("%d", &in); if(st[in+1]==0){ st[in]++; cnt++; continue; } st[in+1]--; st[in]++; } printf("%d\n", cnt); return 0; }