C++ 백준 16435번 : 스네이크버드

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

16435번: 스네이크버드

문제

스네이크버드는 뱀과 새의 모습을 닮은 귀여운 생물체입니다. 

스네이크버드의 주요 먹이는 과일이며 과일 하나를 먹으면 길이가 1만큼 늘어납니다.

과일들은 지상으로부터 일정 높이를 두고 떨어져 있으며 i (1 ≤ i ≤ N) 번째 과일의 높이는 hi입니다. 

스네이크버드는 자신의 길이보다 작거나 같은 높이에 있는 과일들을 먹을 수 있습니다.

스네이크버드의 처음 길이가 L일때 과일들을 먹어 늘릴 수 있는 최대 길이를 구하세요.

입력

첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다.

두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다.

출력

첫 번째 줄에 스네이크버드의 최대 길이를 출력합니다.

---

풀이

그리디 문제이며 과일을 오름차순 정렬한 후 그 때 그 때 과일을 먹을 수 있는지 판단한다. 현재 스네이크버드의 길이보다 더 높은 위치의 과일이 있으면 종료한다. (더 이상 먹을 수 없음)

---

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int cnt; cin >> cnt; // 과일의 개수
	int leng; cin >> leng; // 스네이크버드의 초기길이
	vector<int> v;
	while (cnt--) {
		int tmp; cin >> tmp;
		v.push_back(tmp);
	}

	sort(v.begin(), v.end()); // 오름차순 정렬

	for (int i = 0; i < v.size(); i++) {
		if (leng >= v[i]) { // 비교해서 길이가 더 길면 과일 먹음.
			leng++;
		}
		else { // 더 이상 먹을 과일이 없을 때
			break;
		}
	}

	cout << leng << '\n';

	return 0;
} //main