[백준 30892] 상어 키우기 (C++)

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

30892번: 상어 키우기

문제

---

인천대학교의 앞바다에는 N마리의 상어가 살고 있다고 한다. 각각의 상어는 서로 같거나 다른 크기의 몸집 Ai를 가지고 있다. 상어의 세계는 완전한 약육강식의 세계로, 상어 자신의 크기보다 작은 상어는 전부 먹을 수 있다. 이때, 상어의 크기는 잡아먹힌 상어의 크기만큼 커지게 된다. 반면, 자신의 크기 이상인 상어는 전혀 잡아먹지 못한다.

어느 날 크기가 T인 샼이라는 이름의 아기 상어는 인천대학교 앞바다에 존재하는 N마리 상어들의 크기 정보를 모두 입수했다. 똑똑한 아기 상어 샼은 인천대학교 앞바다에 있는 상어들을 최대 K마리까지 적절한 순서로 잡아먹고, 자신의 몸집을 최대로 키울 계획을 하고 있다.

샼이 최선의 선택으로 최대 K마리의 상어를 적절한 순서로 잡아먹었을 때, 몸집이 최대 얼마까지 커질 수 있는지 구해보자.

 

입력

---

첫째 줄에 인천대학교 앞바다에 존재하는 상어의 마릿수 N과, 샼이 먹을 수 있는 상어의 최대 마릿수 K, 샼의 최초 크기를 나타내는 정수 T가 공백으로 구분되어 주어진다. (1≤ K ≤ N ≤ 200,000, 1 ≤ T ≤ 10⁹)

둘째 줄에는 인천대학교 앞바다에 존재하는 N마리의 상어 크기를 나타내는 정수 A_i가 각각 공백으로 구분되어 주어진다. (1 ≤ A_i ≤ 10⁹)

 

출력

---

샼이 최선의 선택으로 최대 K마리의 상어를 적절한 순서로 잡아먹었을 때, 몸집이 최대 얼마까지 커질 수 있는지 출력하시오.

정답은 32비트 정수 변수(int) 범위를 초과할 수 있기 때문에 64비트 정수 변수(C/C++ : long long, JAVA : long)를 사용해야 한다.

 

문제 풀이

---

잡아 먹을 수 있는 것 중 가장 큰 상어를 잡아먹으면 되는 그리디 문제. 오름차 순 정렬 후 샼보다 작은 상어들을 스택에 넣고, 같거나 큰 상어들을 큐에 넣은 후, 스택의 top(오름차순이므로 가장 나중에 push된 상어가 가장 크다.)에 해당하는 상어를 잡아먹는다. 샼은 몸집이 top만큼 커지고, 큐의 상어 중에 현재 샼보다 몸집이 작은 상어들을 꺼내 스택에 넣는다. 이를 K번 반복하면 샼이 얻을 수 있는 최대 몸집이 된다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;

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

	long long N, K, T;
	cin >> N >> K >> T;
	long long* arr = new long long[N];
	stack<long long> smaller;
	queue<long long> bigger;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);
	for (int i = 0; i < N; i++)
	{
		if (arr[i] < T)
		{
			smaller.push(arr[i]);
		}
		else
		{
			bigger.push(arr[i]);
		}
	}
	for (int i = 0; i < K; i++)
	{
		if (smaller.empty())
		{
			break;
		}
		else
		{
			long long currentTop = smaller.top();
			T += currentTop;
			smaller.pop();
			while (!bigger.empty() && T > bigger.front())
			{
				long long nextSize = bigger.front();
				bigger.pop();
				smaller.push(nextSize);
			}
		}
	}
	cout << T << "\n";
	return 0;
}