[G5] 백준 11509번 풍선 맞추기 C++ 그리디 알고리즘

리뷰

 

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

골드 난이도 문제는 아닌 것 같다. 별도로 정렬이 필요한 그리디도 아니고 단순 아이디어 구현인듯

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• cnt : 높이별 풍선 개수를 저장할 배열
• n : 풍선의 개수를 저장할 변수

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, 변수 ans를 0으로 초기화한다.
2. n개의 풍선 높이를 매번 변수 h에 입력받는다.
3. cnt[h+1]이 1이상이면 cnt[h+1]을 감소시키고, cnt[h]를 증가시킨다.
4. cnt[h+1]이 0이면 cnt[h]를 증가시키고, ans를 증가시킨다.
5. ans에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 현재 입력받은 풍선의 높이보다 1더 높은 풍선이 있는 경우 현재 풍선은 자동으로 터뜨릴 수 있다.
2. 현재 입력받은 풍선의 높이보다 1더 높은 풍선이 없는 경우 별도의 화살을 던져주어야 현재 풍선을 터뜨릴 수 있다.
3. 모든 풍선을 터뜨리는 작업은 왼쪽에서 오른쪽이므로 순서를 고려해주어야 한다.

 

정답 코드

#include<iostream>
using namespace std;

const int N = 1e6 + 1;
int cnt[N];
int n;

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

	cin >> n;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		int h; cin >> h;
		if (cnt[h + 1]) {
			--cnt[h + 1];
			++cnt[h];
		}
		else {
			++cnt[h];
			ans++;
		}
	}
	cout << ans;
}